Favorite Tree

Interview

Time limit0.1sMemory limit1024 MB

Summary

Given two trees T1 and T2, decide whether T1 contains a connected subtree that is isomorphic to T2.

Level: Medium6 of 10
Topics: Tree, DFS, Hash map
Solved: No attempts yet

Problem

Telio learned about tree isomorphism and then wondered how many trees out there contain his favorite tree.

Given two trees $T_1$ and $T_2$ , determine whether $T_1$ has a subtree that is isomorphic to $T_2$ .

Two trees are isomorphic if their vertices can be labeled so that the two trees become exactly the same. For example, a tree with edges $\{(1, 2),(2, 3)\}$ is isomorphic to a tree with edges $\{(1, 3),(3, 2)\}$ .

The figure below shows $T_1$ on the left and $T_2$ on the right. The subtree of $T_1$ formed by all vertices except vertex 5 is isomorphic to $T_2$ .

Input

The input has two groups of lines. The first group describes $T_1$ , and the second group describes $T_2$ .

Each group starts with an integer $N$ ( $1 \le N \le 100$ ), the number of vertices. Vertices are labeled with distinct integers from 1 to $N$ . Each of the next $N-1$ lines contains two integers $U$ and $V$ ( $1 \le U, V \le N$ , $U \ne V$ ), meaning the tree has the edge $(U, V)$ .

The input always describes two valid trees.

Output

Print a single line containing the uppercase letter "Y" if $T_1$ has a subtree isomorphic to $T_2$ , and "N" otherwise.

Examples3

Example 1
Input
```
5
1 3
4 5
3 2
3 4
4
2 4
2 1
3 2
```
Expected output
```
Y
```
Example 2
Input
```
4
2 3
2 1
2 4
4
1 2
2 3
3 4
```
Expected output
```
N
```
Example 3
Input
```
1
1
```
Expected output
```
Y
```