beecrowd | 3447

Favorite Tree

By Sociedade Brasileira de Computação (SBC), ICPC Latin American Regional – 2022 BR Brazil

Timelimit: 1

After learning about tree isomorphism, Telio couldn’t avoid but wonder in how many trees out there his favorite tree is hiding.

Given two trees, T1 and T2, can you help him determine if there is a subtree of T1 isomorphic to T2?

Two trees are isomorphic if it is possible to label their vertices in such a way that they become exactly the same tree. For instance, a tree having edges {(1,2),(2,3)} is isomorphic to a tree having edges {(1,3),(3,2)}.

The figure below corresponds to the first sample, with tree T1 on the left and tree T2 on the right. The subtree of T1 formed by all of its vertices but vertex 5 is isomorphic to T2.

beecrowd

Input

There are two groups of lines, each group describing a tree. The first group describes the tree T1, while the second group describes the tree T2.

Within each group describing a tree, the first line contains an integer N (1 ≤ N ≤ 100) representing the number of vertices in the tree. Vertices are identified by distinct integers from 1 to N. Each of the next N-1 lines contains two integers U and V (1 ≤ U, V ≤ N and U ≠ V ), indicating that the tree has the edge (U,V).

It is guaranteed that the input describes two valid trees.

Output

Output a single line with the uppercase letter “Y” if there is a subtree of T1 that is isomorphic to T2, and the uppercase letter “N” otherwise.

Input Samples Output Samples

5

1 3

4 5

3 2

3 4

4

2 4

2 1

3 2

Y

4

2 3

2 1

2 4

4

1 2

2 3

3 4

N

1

1

Y