URI Online Judge | 1229

Combating Cancer

Maratona de Programação da SBC Brazil

Timelimit: 2

Researchers from the Foundation Against Cancer (FCC) announced a revolutionary discovery in Chemistry: they discovered how to make carbon atoms bind to any number of other carbon atoms, enabling the creation of more complex molecules than those formed by tetravalent carbon. According to the FCC, this will allow the development of new drugs that may be crucial in fighting cancer.

Currently, the FCC can only synthesize molecules that have a single bonds between the carbon atoms and contain no cycles in their structures: for example, the FCC can synthesize molecules (a), (b) and (c) below, but not the molecule (d).


Due to thermal agitation, the same molecule can take several formats. Two molecules are equivalent if it is possible to move the atoms of the molecules, without breaking any of the existing chemical bonds or creating new chemical bonds, so that both molecules are exactly equal. For example, in the figure above, molecule (a) is not equivalent to molecule (b), but is equivalent to molecule (c).

You should write a program that, given the structures of two molecules, determines if they are equivalent.

Input

The input contains several test cases. The first line of a test case contains an integer N indicating the number of atoms in the two molecules. The atoms are identified by integers from 1 to N (2 ≤ N ≤ 104). Each the following 2N − 2 lines describes a chemical bonds between two atoms: the first N − 1 lines describe the chemical bonds of the first molecule, the last N −1 lines describe the chemical bonds of the second molecule. Each line contains two integers A and B indicating that a chemical bond exists between atoms A and B.

Output

For each test case your program must print a single line, containing a single character: S if the molecules are equivalent or N otherwise.

Sample Input Sample Output

7
1 2
2 3
3 4
4 5
6 2
7 3
1 2
2 3
3 4
4 5
6 2
7 4
6
1 2
1 3
2 4
2 5
3 6
2 4
5 3
6 4
1 4
5 6

N
S