VERTEX COVER is a famous NP-complete problem. In VERTEX COVER you are given a graph and you should choose a minimum size subset of its vertices such that for each edge at least one of its endpoints is in the subset.

Given a connected graph with $n$ vertices and $n + 1$ edges, find the size of its minimum vertex cover.

Input

The first line contains one integer, $n$. Next $n+1$ lines each contain two integers, $v_i$ and $u_i$ meaning that there is an edge between vertices $v_i$ and $u_i$. The graph is connected.

Output

Output the size of the minimum vertex cover.

Constraints

• $4 \le n \le 10^5$
• $1 \le v_i, u_i \le n$, $v_i \neq u_i$

Examples

Input:

4
1 2
2 3
3 4
2 4
1 3

Output:

2

We can choose $\{2, 3\}$ as the vertex cover.