Canadian Computing Competition: 2008 Stage 2, Day 1, Problem 3

Fred is a baby. Above Fred's crib hangs a mobile. Fred is amused by this mobile. Fred has a twin sister, Mary. Above Mary's crib hangs another mobile. Fred wonders whether the mobile above his crib and the mobile above Mary's crib are the same. Help Fred.

A mobile is a collection of bars, strings, and decorative weights suspended from the ceiling. Each bar is suspended by a string tied to the exact centre of the bar. From each end of a bar hangs a string that is tied either to another bar or to a weight. The bars can rotate freely about their centres. Fred cannot tell two bars apart, even if they have different lengths. Fred also cannot tell two strings apart. Fred therefore considers two mobiles to be the same if the bars of one mobile can be rotated somehow to make the two mobiles appear identical.

Fred has even developed a notation for describing mobiles. He assigns each bar a distinct positive integer from ~1~ to the number of bars in the mobile, and he assigns the various objects negative integers. ~1~ always represents the bar suspended from the ceiling. (So, for example, a biplane might be represented by Fred as object ~-2~, a crescent-moon might be object ~-57~, and a star might be object ~-21~.) Fred can only count down to ~-9\,999~, so you can assume that he gave no objects lower numbers than ~-9\,999~.

Input Specification

The input contains two mobile descriptions. The first line of a mobile description contains a single nonnegative integer ~n~ ~(1 \le n \le 100\,000)~, indicating the number of bars in the mobile. On the next ~n~ lines, there are two numbers per line, with these two numbers representing the objects hanging from bar ~i~.

Output Specification

Output is composed of one line. Write Fred and Mary have different mobiles. if Fred's information is enough to distinguish the two mobiles; otherwise, Fred and Mary might have the same mobile..

Sample Input 1

5
2 3
4 5
-1 -2
-3 -4
-5 -6
5
2 5
-1 -2
-3 -4
-5 -6
3 4

Sample Output 1

Fred and Mary might have the same mobile.

Sample Input 2

5
2 3
4 5
-3 -4
-1 -2
-5 -6
5
2 5
-1 -2
-3 -4
-5 -6
3 4

Sample Output 2

Fred and Mary have different mobiles.

Grading

Half of all marks will have ~n \le 200~. ~75\%~ of the marks will be from test cases with ~n \le 5\,000~.
All test cases will have ~n \le 100\,000~.