2008 Canadian Computing Competition, Day 1

Day 1, Problem 3: Mobile

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 -9999, so you can assume that he gave no objects lower numbers than -9999.

Input

The input contains two mobile descriptions. The first line of a mobile description contains a single nonnegative integer n (1 ≤ n ≤ 100000), 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

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

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

Sample Output

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 ≤ 200. 75% of the marks will be from test cases with n ≤ 5000.
All test cases will have n ≤ 100000.
Your solution must use at most 1 second of CPU time and at most 512MB of memory.

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 1.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)

Is my solution really intended to pass? It seems a little too easy. I wasn't really aware of it when I first submitted, but in hindsight my code looks kind of silly.

I would humbly suggest that time limit be lowered or that the problem be re-valued - or perhaps that some harder cases be added.

[I am referring to my first submission from last year]

I agree that the problem is a bit overvalued. To that end, I've dropped the point value to 20.