Problem Statement

There is an undirected connected graph consisting of $N$ vertices, $N - 1$ red edges, and $N - 1$ black edges.

The vertices are numbered from $1$ to $N$. The $i$-th red edge connects vertices $A_i$ and $B_i$ bidirectionally, and the $j$-th black edge connects vertices $C_j$ and $D_j$ bidirectionally.

It is guaranteed that the graph consisting only of the red edges and the graph consisting only of the black edges are each connected.

Starting from a vertex of your choice, you will perform the following move some number of times: freely choose one edge connected to the current vertex and move along it to the adjacent vertex.

Red edges never break no matter how many times they are traversed, but a black edge breaks once it is traversed and can no longer be traversed.

Find the minimum number of moves required to break all the black edges.

Input

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_{N-1}$ $B_{N-1}$
$C_1$ $D_1$
$C_2$ $D_2$
$:$
$C_{N-1}$ $D_{N-1}$

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_j, D_j \leq N$
• The graph consisting only of the red edges and the graph consisting only of the black edges are each connected
• All input values are integers

Output

Output the answer on $1$ line.

Sample

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

5

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

3