Reorder Routes to Make All Paths Lead to the City Zero

The underlying undirected graph is a tree, and each edge is currently one-way. Edges may be reversed so that every city can reach the capital, city 0. Find the minimum number of reversals.

This site uses a standard input/output protocol.

输入格式

The first line contains N (2..50000), followed by N−1 lines a b, each meaning a→b; 0≤a,b<N, a≠b, and the underlying graph is guaranteed to be a tree.

输出格式

Output a single integer, the answer.

样例 1

输入：

6
0 1
1 3
2 3
4 0
4 5

输出：

3

样例 2

输入：

5
1 0
1 2
3 2
3 4

输出：

2

样例 3

输入：

3
1 0
2 0

输出：

0

样例说明

Example 1: 0→1, 1→3, and 4→5 must be reversed, for 3 in total. Example 2: 1→2 and 3→4 must be reversed, for 2 in total. Example 3: every edge already points toward 0, so 0 reversals.