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.