atcoder#AGC009B. Tournament
Tournament
Score : points
Problem Statement
contestants participated in a competition. The total of matches were played in a knockout tournament. For some reasons, the tournament may not be "fair" for all the contestants. That is, the number of the matches that must be played in order to win the championship may be different for each contestant. The structure of the tournament is formally described at the end of this statement.
After each match, there were always one winner and one loser. The last contestant standing was declared the champion.
Figure: an example of a tournament
For convenience, the contestants were numbered through . The contestant numbered was the champion, and the contestant numbered was defeated in a match against the contestant numbered .
We will define the depth of the tournament as the maximum number of the matches that must be played in order to win the championship over all the contestants.
Find the minimum possible depth of the tournament.
The formal description of the structure of the tournament is as follows. In the -th match, one of the following played against each other:
- Two predetermined contestants
- One predetermined contestant and the winner of the -th match, where $j(j was predetermined
- The winner of the -th match and the winner of the -th match, where and $(j,k were predetermined
Such structure is valid structure of the tournament, if and only if no contestant who has already been defeated in a match will never play in a match, regardless of the outcome of the matches.
Constraints
- It is guaranteed that the input is consistent (that is, there exists at least one tournament that matches the given information).
Input
The input is given from Standard Input in the following format:
:
Output
Print the minimum possible depth of the tournament.
5
1
1
2
4
3
The following tournament and the result of the matches are consistent with the given information:
- In the first match, contestants and played against each other, and contestant won.
- In the second match, contestants and played against each other, and contestant won.
- In the third match, contestants and played against each other, and contestant won.
- In the fourth match, contestants and played against each other, and contestant won.
The depth of this tournament is , since contestant must play three matches in order to win the championship. There is no tournament with depth or less that is consistent with the given information, thus the output should be .
7
1
2
1
3
1
4
3
4
4
4
1
3