← 返回题目列表

Codeforces · 238/C

C. 吞世者兄弟

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

你一定听说过梦想统治世界的两兄弟。之前的计划全部失败,这一次他们决定联手统治世界。

如你所知,世界上有n个国家。这些国家由 n - 1 条有向道路连接。如果不考虑道路的方向,世界上每对国家之间都有一条独特的路径,每条道路最多经过一次。

兄弟俩都想在某个国家建立自己的统治,那么他就有可能控制从他的国家通过有向道路可以到达的国家。

如果最多存在两个国家可供兄弟选择(并在这些国家建立统治),并且任何其他国家至少受其中一个国家的控制,则兄弟可以统治世界。为了实现这一点,他们希望改变最少数量的道路的方向。您的任务是计算最少的道路数量。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 3000)。接下来的 n - 1 行中的每一行都包含两个以空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi),表示有一条从国家 ai 到国家 bi 的道路。

考虑国家从 1 到 n 编号。可以保证,如果不考虑道路的方向,世界上每对国家之间都有一条独特的路径,每条道路最多经过一次。

输出

在唯一的输出行中打印出应该改变方向的最少道路数,以便兄弟能够统治世界。

示例

输入 #1

4
2 1
3 1
4 1

输出 #1

1

输入 #2

5
2 1
2 3
4 3
4 5

输出 #2

0