本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1237. H. Knights Airways


Description

“This is Knights Airways Flight 472 requesting permission to take off…over…kshh.”  Knights Airways was recently created to take UCF Knights to their vacation destinations at a cost every college student can afford.  One day, while trying to get to his favorite travel spot, Knights Airways owner Uppin Diare realized there was a problem.  His flight from Orlando arrived into Tampa on time, but his connecting flight from Tampa to Miami had already taken off.  Not wanting other travelers to experience this, Mr. Diare wants flights to be ordered in such a way that no passenger would miss their connections.  Mr. Diare has asked you to determine a flight ordering that would prevent people from experiencing the annoyances of a missed connection.  Note that this flight ordering will dictate from which cities passengers can fly to which other cities.  For example, if the flight ordering puts the flight from City A to City B before the flight from City B to City C, then passengers can fly from A to B, B to C, and A to C.                                                                                                                             
 
The Problem:
 
Given a list of flights, determine an ordering that would allow all passengers flying into a city to arrive before the departure of the flights leaving the same city.  You may assume that no traveler, once departing a city, can make any number of connecting flights and return back to their origin.

Input

The first input line contains a positive integer, n, indicating the number of flight schedules to order.  The description of each flight schedule is as follows: Each flight schedule will start with a line containing a single integer, f (1 ≤ f ≤ 10,000), which is the number of flights for the given schedule.  The following f lines will contain the origin city, destination city, and flight number for each flight, each separated by a single space.  There will be no leading or trailing spaces on any input line.  All cities will consist of up to 25 uppercase letters.  Multiple flights from the same origin city to the same destination city may exist, but will have different flight numbers. All flight numbers for a given flight schedule will be unique positive integers less than 100,000 with no leading zeros.

Output

For each flight schedule, on a single line, output the ordered flight numbers separated by a space.  If there are multiple ways of ordering the flights, choose the ordering that comes first numerically based on flight numbers.  You are guaranteed that each flight schedule will produce one unique answer.  Note that all the flights in the input will be in the output.  In particular, when there are multiple flights from the same origin city to the same destination city, every one of these flights will be listed in the output.

Samples

Input Copy
2
7
TAMPA MIAMI 912
ORLANDO TAMPA 450
MIAMI ATLANTA 321 
ATLANTA NEWYORK 942 
ORLANDO ATLANTA 952  
CHICAGO MIAMI 568 
MIAMI ATLANTA 64 
3 
ATLANTA TAMPA 351 
MIAMI NEWYORK 135 
ORLANDO CHICAGO 531 
Output
450 568 912 64 321 952 942 
135 351 531

Source

UCF2013
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1027. UCF 2013
My history solutions

You didn't submit any solution!
Submit your solution

Login Register