Problem Description

Given a tree with $n$ nodes, the nodes are numbered from $1$ to $n$.

Now you need to cut (remove) two edges. This will split the tree into three connected components. Suppose the numbers of nodes in these three components are $a, b, c$. Your task is to minimize $\max\{a,b,c\}-\min\{a,b,c\}$, and output this minimum value.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.
The next $n-1$ lines each contain two integers $x, y$, representing an edge of the tree.

Output Format

Output one integer in a single line, representing the answer.

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

Hint

Sample 1 Explanation

An optimal solution can make the sizes of the three connected components $1,1,2$, so the output is $2-1=1$.

Sample 2 Explanation

Cut the edge between node $1$ and node $3$, and the edge between node $3$ and node $5$. The three resulting connected components have the same number of nodes.

Sample 3 Explanation

As shown in the figure below:

Constraints

This problem uses bundled testdata.

• Subtask 1 (15 pts): $3 \le n \le 200$.
• Subtask 2 (35 pts): $3 \le n \le 2000$.
• Subtask 3 (60 pts): $3 \le n \le 2 \times 10^5$.

For $100\%$ of the testdata, $1 \le x,y \le n$.

The full score for this problem is $110$ points.

Notes

Translated from Croatian Open Competition in Informatics 2020 ~ 2021 Round 1 D Papričice 。

Translated by ChatGPT 5