F. Favorite Tree
time limit per test
0.5 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

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, $$$T_1$$$ and $$$T_2$$$, can you help him determine if there is a subtree of $$$T_1$$$ isomorphic to $$$T_2$$$?

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 $$$T_1$$$ on the left and tree $$$T_2$$$ on the right. The subtree of $$$T_1$$$ formed by all of its vertices but vertex $$$5$$$ is isomorphic to $$$T_2$$$.

Input

There are two groups of lines, each group describing a tree. The first group describes the tree $$$T_1$$$, while the second group describes the tree $$$T_2$$$.

Within each group describing a tree, the first line contains an integer $$$N$$$ ($$$1 \leq N \leq 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 \le U,V \le N$$$ and $$$U \neq 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 $$$T_1$$$ that is isomorphic to $$$T_2$$$, and the uppercase letter "N" otherwise.

Examples
Input
5
1 3
4 5
3 2
3 4
4
2 4
2 1
3 2
Output
Y
Input
4
2 3
2 1
2 4
4
1 2
2 3
3 4
Output
N
Input
1
1
Output
Y