题目描述

Afrika paprika! – S.V.

经过一整个早晨在花园中的劳累，Malnar 先生决定用他自己种的干辣椒奖赏自己。

他拥有 $n$ 个辣椒，用 $n - 1$ 条细绳链接，且满足任意两个辣椒都能通过若干细绳连接。形式化地说，它们形成了一棵树。

Malnar 先生今天将享用三餐。为此，他会切断两条细绳，以获得三个更小的连通分量，每餐吃一个。

让一餐太辣是不好的，所以他会选择一种切割方式，最小化最大连通分量的大小与最小连通分量的大小之差。你需要求出这个差值。

输入格式

第一行一个正整数 $n$，表示辣椒的数量。辣椒从 $1$ 到 $n$ 编号。
接下来 $n - 1$ 行，每行两个正整数 $x, y$（$1 \le x, y \le n$），表示用一根细绳直接连接的两个辣椒的编号。

输出格式

输出最小的连通块大小之差。

4
1 2
2 3
3 4

1

在样例 1 中，三种可能的切割方式都会切出一个有两个辣椒的连通分量和两个有一个辣椒的连通分量。所以答案为 $2 - 1 = 1$。

6
1 2
1 3
3 4
3 5
5 6

0

在样例 2 中，切断连接辣椒 $1, 3$ 和 $3, 5$ 之间的细绳，就可以让三个连通分量的大小都相同，所以答案为 $0$。

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

2

样例 3 的最优切割方式在题目描述中已经展示。三个连通分量的大小分别为 $4$、$2$ 和 $3$，答案为 $4 - 2 = 2$。

数据范围与提示

译者：PinkRabbit