Problem Description

Given a tree with \( n \) nodes, numbered from 1 to \( n \).

You need to choose two edges to remove, which will form three connected components. Let the number of nodes in these three components be \( a, b, c \). Your task is to minimize the value of \( \max\{a, b, c\} - \min\{a, b, c\} \) and find this minimum value.

Input Format

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

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

4
1 2
2 3
3 4

Sample Output #1

1

Sample Input #2

6
1 2
1 3
3 4
3 5
5 6

Sample Output #2

0

Sample Input #3

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

Sample Output #3

2

Notes

Sample 1 Explanation

The optimal solution forms three connected components with node counts \( 1, 1, 2 \), so the output is \( 2 - 1 = 1 \).

Sample 2 Explanation

By removing the edge between node \( 1 \) and node \( 3 \), and the edge between node \( 3 \) and node \( 5 \), the three connected components have equal node counts.

Sample 3 Explanation

Refer to the diagram provided in the original problem statement.

Data Constraints

This problem uses subtask testing.

• 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 data, \( 1 \le x, y \le n \).

This problem is worth a total of 110 points.

Notes

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

见题面 Input 部分

见题面 Output 部分