Problem Description

A teacher has a tree with $n$ nodes, numbered $1,2,\ldots,n$ in order.

The teacher wants to give this tree as a prize to two students. Specifically, the teacher will choose one edge and delete it from the tree, thereby splitting the tree into two connected components. Each student will receive one of the connected components.

If one student gets a component whose number of nodes is obviously smaller than the other student's, that student may feel unhappy. To avoid this, the teacher wants to know what the minimum possible absolute difference between the sizes (number of nodes) of the two components is.

Input Format

The first line contains a positive integer $n$, representing the number of nodes.

The next $n-1$ lines each contain two positive integers $u_i, v_i$, representing an edge connecting nodes $u_i$ and $v_i$.

Output Format

Output one line with one integer, representing the answer.

4
1 2
2 3
3 4

0

6
1 2
1 3
1 4
1 5
5 6

2

Hint

For $40\%$ of the testdata, it is guaranteed that $2\le n\le 500$.

For all testdata, it is guaranteed that $2\le n\le 2\times 10^4$.

Translated by ChatGPT 5