Minimize Tree Partition Difference

You are given a tree with n vertices numbered from 1 to n. You need to remove exactly two edges from the tree, which will split the tree into three connected components. Let the sizes (number of vertices) of these components be \(a\), \(b\), and \(c\). Your task is to minimize the value of \(\max\{a,b,c\} - \min\{a,b,c\}\).

Input: The first line contains an integer n representing the number of vertices. Each of the following n-1 lines contains two integers u and v representing an edge connecting vertices u and v.

Output: Print the minimum possible difference \(\max\{a,b,c\} - \min\{a,b,c\}\).

The answer should be formatted using LaTeX for any mathematical expressions.

inputFormat

The input begins with an integer n (the number of nodes). The next n-1 lines each contain two integers \(u\) and \(v\) denoting an edge between nodes \(u\) and \(v\).

Example:

6
1 2
1 3
2 4
2 5
3 6

outputFormat

Output a single integer representing the minimum possible value of \(\max\{a,b,c\} - \min\{a,b,c\}\) after removing two edges.

Example:

2

sample

6
1 2
1 3
2 4
2 5
3 6

2