Minimum Edge Reversals to Root a Tree

You are given a tree where every edge currently has a direction. Choose any node as the root; all edges must end up pointing away from the root. Reversing one edge costs 1. Find the minimum total cost.

This site has made the standard input and output explicit.

输入格式

The first line contains n, followed by n−1 lines of directed edges u v, 0-based. On this site 1≤n≤200000, and ignoring directions the graph must be a tree.

输出格式

Output one integer, the answer.

样例 1

输入：

3
0 1
2 1

输出：

1

样例 2

输入：

3
0 1
1 2

输出：

0

样例 3

输入：

1

输出：

0

样例说明

Example 1: whether 0 or 2 is the root, only 1 edge needs reversing, so the minimum is 1. Example 2: with 0 as the root all edges already point outward, so output 0. Example 3: there are no edges, so nothing needs reversing.