← 返回题目列表

Codeforces · 581/F

F. Zublicanes 和 Mumocrates

中文机器翻译题面 查看原题

现在是伯兰的选举时间。最受喜爱的当然是 zublicanes 和 mumocrates 的派对。两党的竞选活动包括在贝尔兰首都n个主要广场举行多次示威活动。 n个广场中的每个广场当然只能有一个政党的示威活动,否则可能会导致骚乱。另一方面,双方都申请举办大规模示威活动,所有广场都必须举行示威活动。现在资管会将面积分配给双方。

一些广场对由 (n - 1) 条双向道路连接,因此在任何一对广场之间都有一种独特的方式从一个广场到达另一个广场。有些广场位于首都郊区,这意味着它们通过一条路仅与另一个广场相连,这种广场被称为死胡同广场。

首都市长指示在双方之间分配所有广场,以便死胡同广场上第一方和第二方的示威次数相同。保证城市的死胡同方格数量是偶数。

为了防止 zublicanes 和 mumocrates 之间可能发生的冲突,决定尽量减少连接广场和不同政党的道路数量。作为分配方块部门的开发人员,您应该确定这个最小的数字。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 5000) — Berland 首都的正方形数量。

接下来的 n - 1 行包含整数对 x, y (1 ≤ x, y ≤ n, x ≠ y) — 由道路连接的方格的数量。所有方块都用 1 到 n 的整数进行编号。保证城市的死胡同方格数量是偶数。

输出

打印一个数字——连接不同政党示威广场的最少道路数量。

示例

输入 #1

8
1 4
2 4
3 4
6 5
7 5
8 5
4 5

输出 #1

1

输入 #2

5
1 2
1 3
1 4
1 5

输出 #2

2