Hide

Problem B
Brilliance of Wings

Mashiro has a tree with $N$ vertices and $N - 1$ unweighted edges. It is known that any two vertices in the tree are connected.

Mashiro wants to perform a Morfonication on the tree. To put it simply, Mashiro will do several operations to transform the original tree to a new tree to her liking. Each operation Mashiro does is of the following:

  • Select an edge from the tree and remove it. After this step, the tree becomes disconnected to two components.

  • Add an edge between any two vertices such that the structure is reconnected into a tree.

After every operation Mashiro does, the tree must stay as a tree, meaning it must have exactly $N - 1$ edges and any two vertices in the tree are connected.

Mashiro doesn’t have a lot of time since she’s late for practice. Can you help her find the minimum number of operations to do so?

Input

The first line of input contains one integer $N$ $(2 \leq N \leq 10^5)$, the size of the two trees.

The second to $N$-th lines of the input contain two integers $U_i$ and $V_i$ $(1 \leq U_i, V_i \leq N, U_i \ne V_i)$, the edges of the first tree.

The $(N+1)$-th to $(2N - 1)$-th lines of the input contains two integers $X_i$ and $Y_i$ $(1 \leq X_i, Y_i \leq N, X_i \ne Y_i)$, the edges of the second tree.

Output

Output one line containing one integer denoting the minimum number of operations.

Sample Input 1 Sample Output 1
4
1 2
2 3
3 4
3 1
4 1
2 4
3

Please log in to submit a solution to this problem

Log in