MFMOBILE - Mobile (Again)

no tags 

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.".

Example #1

Input:
5 
2 3 
4 5 
-1 -2 
-3 -4 
-5 -6 
5 
2 5 
-1 -2 
-3 -4 
-5 -6 
3 4

Output:
Fred and Mary might have the same mobile.

Example #2

Input:
5
2 3
4 5
-3 -4
-1 -2
-5 -6
5
2 5
-1 -2
-3 -4
-5 -6
3 4

Output:
Fred and Mary have different mobiles.

hide comments
JaceTheMindSculptor: 2009-04-13 21:29:35

The first line of each mobile indicates how many bars there are. The first line of the mobile description indicates the two objects/bars hanging from bar 1. THe second line, the objects/bars hanging fomr bar 2.

JaceTheMindSculptor: 2009-04-13 21:24:08

Thanks, Neal Wu. That problem has been fixed.

Neal Wu: 2009-04-13 21:23:35

The first example is wrong. It should be
5
2 3
4 5
-1 -2
-3 -4
-5 -6
5
2 5
-1 -2
-3 -4
-5 -6
3 4

Sudharssun: 2009-04-13 21:23:35

Can u pl giv me an explanation of the input format??


Added by:JaceTheMindSculptor
Date:2009-04-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Canadian Computing Competition 2008 Stage 2 Day 1 Problem C