Afrika paprika! – S.V.

在花园里度过了一个疲惫的上午后，Malnar 先生决定用自己种植的干辣椒来奖励自己。

他有 $n$ 个辣椒，由 $n - 1$ 根绳子连接，使得任意两个辣椒都通过一系列绳子相连。形式上，它们构成了一棵树。

Malnar 先生今天将享用三顿午餐。为此，他将切断两根绳子，以获得三个较小的连通块，每顿午餐分得一个连通块。

第三个样例中的树以及最优切法。

任何一顿午餐太辣都不好，因此他会选择一种切法，使得最大连通块和最小连通块的大小之差最小。你需要求出这个最小差值。

输入格式

第一行包含一个整数 $n$，表示辣椒的数量。辣椒用 $1$ 到 $n$ 的整数编号。

接下来的 $n - 1$ 行，每行包含两个整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示由一根绳子直接相连的两个辣椒的编号。

输出格式

输出可能的最小连通块大小差值。

子任务

样例

输入 1

4
1 2
2 3
3 4

输出 1

1

输入 2

6
1 2
1 3
3 4
3 5
5 6

输出 2

0

输入 3

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

输出 3

2

说明

在第一个样例中，切断绳子的三种可能方式中的每一种都会产生一个包含两个辣椒的连通块和两个各包含一个辣椒的连通块。因此答案为 $2 - 1 = 1$。

在第二个样例中，通过切断连接辣椒 $1$ 和 $3$ 的绳子，以及连接 $3$ 和 $5$ 的绳子，可以得到三个大小相同的连通块，因此答案为 $0$。

第三个样例的最优切法如题目描述中的插图所示。连通块的大小分别为 $4$、$2$ 和 $3$，答案为 $4 - 2 = 2$。