[BIO99 Logo] The British Informatics Olympiad is
the computing competition for schools and colleges.
We are proud to present BIO'99.
[Data Connection logo]

The 1999 British Informatics Olympiad Final
Spy vs Spy - Part One

Alpha complex is large and sprawling, its many rooms and corridors designed to confuse the uninitiated. Corridors are clearly marked with their security level (a to z), but the rooms are essentially indistinguishable; all complicated machinery looks the same, as do all complicated technicians. The only way to move between two rooms is through a connecting corridor. The security doors leading from the rooms to the corridors sometimes only open in one direction, so a route from A to B does not necessarily mean there is a corresponding route from B to A.

Two spies were sent into Alpha complex and each managed to map out the rooms and their connecting corridors. It is possible that one of the spies got lost (due to budget cuts there was only one compass available) and his map might actually be of Beta complex.

Write a program that reads in the details of the two maps and determines if they are identical. The first line of input will be an integer 1<=n<=100, specifying how many rooms are on each map. The next n lines will contain the first spy's map, and the following n lines the second spy's map.

As each spy explored the complex they labelled the rooms from 1 to n, their sophisticated equipment enabling them to identify rooms they had already entered so each room received a unique label. Unfortunately they each used different equipment, so the two labellings are not necessarily the same.

The ith line of a spy's map contains details of the rooms directly accessible from room i. Lines consist of letter/number pairs; the letter is the security clearance of the connecting corridor, and the number is the room at the far end. No room has more than one corridor leading away from it with the same security level, and every room has at least one exit. Thanks to convoluted fire regulations, each map always has at least one room from which is is possible to ultimately reach every other room.

Two maps are identical if their only difference is in way the rooms are labelled. If the two maps are identical you should output n integers; the jth of these integers being the label the second spy gives to the room the first spy labels j. If there are multiple solutions you only need to print one. If the two maps are not identical you should just output Different.

Sample Input

a 2
t 5 r 4
a 4
r 2 t 3
b 5 i 5 o 5
a 3
a 4
r 4 t 1
r 3 t 5
b 5 o 5 i 5

Sample Output

2 4 1 3 5

The British Informatics Olympiad