2008 Canadian Computing Competition, Day 1

Day 1, Problem 1: Moving Day

Every year on July 1st, the residents of Quebec experience Moving Day. It is customary for most apartment leases to begin and end on this day, making it a popular time for people to move. The streets are filled with moving trucks and anxious tenants packing and unpacking their belongings, waiting for their truck to become available, or waiting for a previous tenant to vacate their apartment. It is a busy but profitable time for moving companies. You will write a program to help the residents of a small town plan the order in which they should move.

Only one truck is available, so all of the people who are moving must share it. Therefore, the people must move one at a time. A person cannot move into a new house before the former tenant has moved out. Each person moves directly from their old house to their new house; a person may not move temporarily into another vacant house while waiting for their new house to be vacated.

You may assume that no two people are moving into the same house. You may assume that no two people are moving out of the same house. You may also assume that each house to which someone is moving is either vacant or being vacated on Moving Day.

Input

The first line of input contains the number n (1 ≤ n ≤ 100) of people who are moving. Each of the following n lines of input contains a person's name followed by the address that the person is moving from and the address that the person is moving to. Because there is only one street in the town (called Main St.), each address is just a number between 1 and 100, inclusive. You can assume that no name will be longer than 100 characters, and that names contain only alphanumeric characters.

Output

The program should print the names of the people who are moving in the order that they should move. If it is not possible to find an order that ensures that each person's new house is vacant by the time the person moves to it, the program should print only the word "Impossible". If there are several different orders in which the people could move, any valid order is acceptable.

Sample Input

3
Pierre 51 43
Guy 28 83
Marie 43 28

Sample Output

Guy
Marie
Pierre

Grading

All test cases will have 1 ≤ n ≤ 100. Your solution must use at most 512 MB of memory and run in at most 3 seconds.

All Submissions
Best Solutions

Point Value: 10
Time Limit: 3.00s
Memory Limit: 512M
Added: Dec 07, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)