In computer science, NP-Complete (abbreviated as NPC) problems are a class of classic problems combining theoretical depth and computational difficulty—no polynomial-time algorithm has been found for them so far, yet once any one of these problems is conquered, all NP problems will be readily solved.

Little W, who is passionate about algorithm research, has always dreamed of challenging NPC problems. He learned that the famous "Maximum Common Induced Subgraph Problem" in graph theory is a classic NPC problem. Faced with an insurmountable complexity gap on general graphs, Little W decided to take a step back and start with trees, which have a more elegant structure, to study the isomorphic connected subgraph problem on trees.

Specifically, you are given two unrooted trees $T_1$ and $T_2$, each containing $n$ nodes numbered from $1 \sim n$. Little W wants to select a non-empty subset of nodes $V_1$ in $T_1$ and a non-empty subset of nodes $V_2$ in $T_2$, while retaining all original edges in the respective trees between nodes within each subset, thereby inducing two subgraphs $G_1$ and $G_2$, respectively.

Little W requires the two induced subgraphs $G_1, G_2$ to simultaneously satisfy:

1. Connectivity: Both $G_1$ and $G_2$ are connected graphs (in particular, a graph containing only $1$ node is also considered connected).
2. Isomorphism: $G_1$ and $G_2$ are isomorphic. That is, there exists a bijection (one-to-one correspondence) $f : V_1 \to V_2$ from $V_1$ to $V_2$ such that for any $u, v \in V_1$, $u$ and $v$ are connected by an edge in $G_1$ if and only if $f(u)$ and $f(v)$ are connected by an edge in $G_2$. Note: The corresponding nodes $u$ and $f(u)$ are not required to have the same node indices.

Now, Little W hands this simplified problem over to you: what is the maximum number of nodes that the isomorphic connected subgraphs satisfying the above requirements can contain (i.e., find the maximum possible value of $|V_1|$)?

Input

Read the input from stdin.

The first line contains a positive integer $n$, representing the number of nodes in each tree.

The next $n - 1$ lines each contain two positive integers $u, v$, representing an undirected edge $(u, v)$ in tree $T_1$.

The next $n - 1$ lines each contain two positive integers $u, v$, representing an undirected edge $(u, v)$ in tree $T_2$.

Output

Write the output to stdout.

Output a single line containing a positive integer, representing the maximum number of nodes in the selected isomorphic connected subgraphs.

Examples

Input 1

4
1 2
2 3
3 4
1 2
1 3
1 4

Output 1

3

Note

Select the node subset $V_1 = \{1, 2, 3\}$ in $T_1$ and the node subset $V_2 = \{1, 2, 3\}$ in $T_2$. Mapping nodes $1, 2, 3$ in $V_1$ to nodes $2, 1, 3$ in $V_2$ respectively, the two induced subgraphs are both chains containing $3$ nodes, satisfying both connectivity and isomorphism.

Since $T_1$ itself is a chain, any connected subgraph of it must also be a chain; meanwhile, the longest chain in the star graph $T_2$ contains only $3$ nodes, so it is impossible to select isomorphic connected subgraphs with more than $3$ nodes.

Sample 2

See npc/npc2.in and npc/npc2.ans in the contestant directory.

This sample satisfies the constraints of Subtask $1$.

Sample 3

See npc/npc3.in and npc/npc3.ans in the contestant directory.

This sample satisfies the constraints of Subtask $4$.

Sample 4

See npc/npc4.in and npc/npc4.ans in the contestant directory.

This sample satisfies the constraints of Subtask $7$.

Subtasks

For all test data, it is guaranteed that $1 \le n \le 500$, the indices of both endpoints of each edge are between $1 \sim n$, and the two given graphs are both valid trees.

The full score of this problem is $150$ points, and subtask bundled testing is used. You will earn the score of a subtask if and only if you pass all test cases in that subtask. Detailed constraints for each subtask are shown in the table below.

Special Property A: The degree of every node in both trees does not exceed $3$.

Special Property B: There exists an optimal solution whose isomorphism maps node $1$ of $T_1$ to node $1$ of $T_2$.

Special Property C: It is guaranteed that the final answer is at least $n - 1$.

Note: The degree of a node in a tree refers to the number of edges directly incident to that node.