eolymp
Competitions

Azerbaijan 2022: Qualifying exam in the preparation group for the International Olympiad October 29

Koba and banana tree

Your friend Koba is a smart monkey and he loves to eat bananas. He uprooted a banana tree he found this morning in the jungle (Koba is very strong) and carried it to his lair. Koba will have three snacks today. So he thinks about cutting two branches of the tree and splitting it into three parts (he will eat bananas from one of the parts for each snack). Koba wants the difference in the number of bananas between the part with the most bananas and the part with the least bananas to be as small as possible (Koba tries to eat a balanced diet). We will call such a cut an optimal cut.

prb11293.gif

The banana tree that Koba took to his lair is a connected graph consisting of an integer number of bananas numbered from 1 to n and n1 branches - the connecting links between these bananas. That is, we can see bananas as graph vertices, and branches as connections between these vertices.

You are given the structure of a tree that Koba took to his lair. From this, find the difference in the number of bananas between the part with the most bananas and the part with the fewest bananas in the optimal cut.

Input

The first line contains one integer n (3n2 * 105) - the number of bananas. Each of the following n - 1 lines contain two integers ui, vi (1ui, vi*n *) - the pairs of bananas with a straight branch (edge) between them.

Output

Print one integer - the difference in the number of bananas between the part with the most bananas and the part with the least amount of bananas on the optimal cut.

Explanation

Example 1. In this example, if we cut branches between 2 and 3, 4 and 5, then the tree will be divided into three parts of size 2, 2 * and *1. The answer is 21 = 1.

Example 2. The optimal cuts are shown in the figure described above. The dimensions of the parts resulting from cuts are 4, 2 and 3. The answer is 42 = 2.

Time limit 1 second
Memory limit 128 MiB
Input example #1
5
1 2
2 3
3 4
4 5
Output example #1
1
Input example #2
9
1 3
3 2
3 4
3 5
5 6
5 7
7 8
7 9
Output example #2
2
Source Azerbaijan 2022: Qualifying exam in the preparation group for the International Olympiad October 29