All Submissions


Problem Statement

Hacky's Cat is building its own Operating System (that, according to reports from the future, is so awesome that majority of the people prefer that over Windows, Mac and Linux). Hacky wanted to contribute, and so the Cat assigned him a simple problem.

Each module can depend on the existance of other modules on the system. For instance, the module that interprets keystrokes from the keyboard (ie, the device driver) is assumed to exist, and none of the other modules have the same code in them. Instead, they use the services provided by this module. Thus, the "Keyboard Device Driver" is a dependency of "Text Editor" and must be installed before it.

Given a list of modules and their dependencies, calculate the proper order of installation.

Problem Input
  • The first line contains the number of test cases.
  • Each test case is preceeded by a blank line, and consists of a number of lines, separated by spaces.
  • Each line in a test case starts with the name of a module and is followed by the names of all its dependencies.

Problem Output
  • Corresponding to each test case, one line should be output that contains a space separated list of modules in the order they must be loaded.
  • In case multiple modules may be loaded without any problems, the one with the lexographically smallest name should be loaded first. This ensures unique solutions.

Sample Input


2

game keyboard mouse
keyboard usbi
mouse usbi

phpmyadmin apache php mysql arx
apache gcc


Sample Output


usbi keyboard mouse game
arx gcc apache mysql php phpmyadmin


Constraints
  • Module names consist of upto 50 alphanumeric characters.
  • The total number of modules will be less than 200.

Problem Setter: Kaustubh Karkare

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0