|The British Informatics
the computing competition for schools and colleges.
We are proud to present BIO'99.
The 1999 British Informatics
Spy vs Spy - Part Two
You have just heard from your two spies that the budget problems extended to their sophisticated equipment; apparently both pieces of chalk broke. The upshot of the equipment failure is that the spies were unable to know for certain when they entered a room they had been in before. In other words some rooms might occur on a map more than once with different labels. The spies are conscientious, so each version of a room will have the correct number of corridors leading from it.
Write a program that reads in the details of the two maps and determines if they might represent the same complex. The first line will be a pair of integers, 1<=n<=100 then 1<=m<=100, specifying the rooms on each map. The next n lines will contain the first spy's map, and the following m lines the second spy's map. The format for these lines is the same as the previous part.
If the two maps might represent the same complex you should output n lines. The jth line should be a list of all room labels on the second spy's map that correspond to label j on the first spy's map. If there are multiple solutions you only need to print one. If the two maps cannot represent the same complex you should just output Different.
4 6 a 2 x 4 b 3 c 1 a 2 x 1 a 2 x 1 b 3 c 4 a 5 x 4 b 6 c 1
1 4 2 5 3 6 1 4
The simplest map representing this complex would be defined by:
a 2 x 1 b 3 c 1
In other words, either of the two maps in the sample input can be compared wih this map and shown to be equivalent.