题目描述

译自 COCI 2020/2021 Contest #1 T4「Papričice」

Afrika paprika! – S.V.

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

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

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

样例 3 中的树，以及最优切割方式

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

输入格式

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

输出格式

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

4
1 2
2 3
3 4

1

6
1 2
1 3
3 4
3 5
5 6

0

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

2

数据范围与提示

译者：PinkRabbit