URI Online Judge | 1994

Imperialism

By Joaquin Rodrigues, Universidad de Buenos Aires AR Argentina

Timelimit: 1

The ambition of conquest and expansion is a very well known disease in planet Earth... and also in the entire universe.

In planet “Imperius” several fortresses have been built one at a time and each one of them but the first was connected at the moment of its construction to a previously built fortress by a direct path, for commercial purposes.

Imperius was becoming one of the most peaceful and prosperous planet in the universe, until they built no more fortresses. At that moment, N different empires emerged (numbered from 1 to N), each one of them dominating a different fortress. And the thirst of conquest took Imperius. Thus, every year, exactly one of the living empires conquers every neighbor empire, and dominates every fortress belonging to them. Two empires are considered neighbors if there exist two fortresses joined by a path, each one dominated by one different empire of these two.

Eventually a single empire will dominate every fortress. Your task is to find the minimum number of years such that this can happen.

As an example, on the left side of the figure below a possible scenario in which six fortresses are initially dominated by six different empires is shown. Each fortress is tagged with the identification number of the empire dominating it. If empire 2 conquered every neighbor on the first year, the the situation would be as in the central figure. Finally, if empire 5 conquered his neighbor empires, it would end up dominating every fortress, as seen on the right side of the figure.

Input

The input contains several test cases. Each test case is described in two lines. The first line contains an integer N (2 <= N <= 104) representing the number of fortresses in planet Imperius. The next line contains N-1 integers P_i indicating that the fortress i+1 was connected to fortress P_i (1 <= P_i <= i for 1 <= i <=N-1). The last line of the input contains a single -1 and should not be processed as a test case.

Output

For each test case output a single line with an integer representing the minimum number of years such that a single empire may dominate every fortress.

Input Sample Output Sample

6
1 2 2 4 5
7
1 1 3 3 4 4
6
1 2 2 2 2
-1

2
2
1