CF581F.Zublicanes and Mumocrates

It's election time in Berland. The favorites are of course parties of zublicanes and mumocrates. The election campaigns of both parties include numerous demonstrations on n main squares of the capital of Berland. Each of the n squares certainly can have demonstrations of only one party, otherwise it could lead to riots. On the other hand, both parties have applied to host a huge number of demonstrations, so that on all squares demonstrations must be held. Now the capital management will distribute the area between the two parties.

Some pairs of squares are connected by (n - 1) bidirectional roads such that between any pair of squares there is a unique way to get from one square to another. Some squares are on the outskirts of the capital meaning that they are connected by a road with only one other square, such squares are called dead end squares.

The mayor of the capital instructed to distribute all the squares between the parties so that the dead end squares had the same number of demonstrations of the first and the second party. It is guaranteed that the number of dead end squares of the city is even.

To prevent possible conflicts between the zublicanes and the mumocrates it was decided to minimize the number of roads connecting the squares with the distinct parties. You, as a developer of the department of distributing squares, should determine this smallest number.

现在是贝尔兰的选举时间。最受欢迎的当然是祖比利坎党和穆莫克拉特党。两党的竞选活动都包括在贝尔兰首都的 $n$ 个主要广场上举行大量示威游行。每个广场上只能由一个政党举行示威游行，否则可能引发骚乱。另一方面，两党均申请在所有广场上举行大量示威游行，因此所有广场都必须安排示威游行。目前，首都管理部门将负责在两党之间分配这些广场。

某些广场对之间由 $(n-1)$ 条双向道路相连，使得任意两个广场之间都存在唯一的一条路径。某些广场位于首都边缘，即仅通过一条道路与另一个广场相连，这类广场被称为死胡同广场（dead end squares）。

市长指示：需将所有广场分配给两党，使得死胡同广场中属于第一政党和第二政党的数量相等。题目保证该城市的死胡同广场总数为偶数。

为防止祖比利坎党与穆莫克拉特党之间发生潜在冲突，决定最小化连接不同政党所属广场的道路数量。作为负责广场分配部门的开发人员，你需要确定这一最小数量。

The first line of the input contains a single integer n (2 ≤ n ≤ 5000) — the number of squares in the capital of Berland.

Next n - 1 lines contain the pairs of integers x, y (1 ≤ x, y ≤ n, x ≠ y) — the numbers of the squares connected by the road. All squares are numbered with integers from 1 to n. It is guaranteed that the number of dead end squares of the city is even.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 5000$）—— 表示 Berland 首都中广场的数量。

接下来的 $n-1$ 行每行包含一对整数 $x,\,y$（$1 \leq x,\,y \leq n$，且 $x \neq y$）—— 表示由道路连接的两个广场的编号。所有广场均用 $1$ 到 $n$ 的整数编号。保证该城市的死胡同广场数量为偶数。

Print a single number — the minimum number of roads connecting the squares with demonstrations of different parties.

输出一个整数——连接举行不同政党集会的广场的最少道路数量。