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.

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 n − 1 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 (3 ≤ n ≤ 2 * 105) - the number of bananas. Each of the following n - 1 lines contain two integers ui, vi (1 ≤ ui, 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 2 − 1 = 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 4 − 2 = 2.