你一定听说过梦想统治世界的两兄弟。之前的计划全部失败,这一次他们决定联手统治世界。
如你所知,世界上有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