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.
- 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.
- 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.
game keyboard mouse
phpmyadmin apache php mysql arx
usbi keyboard mouse game
arx gcc apache mysql php phpmyadmin
- Module names consist of upto 50 alphanumeric characters.
- The total number of modules will be less than 200.
Problem Setter: Kaustubh Karkare