May be you can remember the "Classmates" problem from the 2004 Urals Programming Contest. The statement of that problem is like follows:
Tanya is a schoolgirl. One day, headmistress asked her to notify the class about next day's
lessons being cancelled due to power outage. Tanya successfully carried out that job. She decided
to call Lena, then Katya, then Masha. While she was calling Katya, Lena, who did already know
the news, called Misha, etc. The whole class knew of the welcome news in almost no time.
The contestants were to determine the minimum time required to pass the news to every
student in the class.
Time passed, and Tanya got a summer internship in the "Advertising, Commercials and Media" agency.
Like any other firm that offers high salaries for students, ACM has a clearly defined hierarchical structure.
The president is the root of the hierarchy. He has some direct subordinates, who themselves can have
direct subordinates, etc. One day, Tanya happened to invent the utterly ingenious method for increasing
the advertisement efectivenes by 110%. She called her boss immediately, then her friend Lena (who was
Tanya's direct subordinate), then Masha and Katya. They, in turn, quickly passed the message to their own
colleagues, and so on. So, you are again to determine the minimum time for the information about Tanya's
method to spread among the entire ACM agency. There is a peculiar feature of the company's phone
network you should take into account. Namely, every employee can only call his/her direct subordinates
or immediate boss (this is supposed to prevent girls from chatting over the phone instead of doing their
work). Each phone call takes exactly one minute.
Input
The first line of input contains the number N of ACM employees (N ≤ 100000). Each employee is assigned
the unique ID number (these numbers range from 1 to N).
N lines follow, K-th line containing zero-terminated space-delimited list of K-th employee's direct subordinates. The last line contains Tanya's ID number. The hierarchical structure is a tree. I.e., each employee has exactly one direct boss, of course, with exception for the topmost boss.
Output
Output consists of one number — the minimum time, in minutes, that is required to propagate Tanya's
idea to all ACM employees.
Sample
input | output |
---|
10
2 3 0
4 5 7 0
6 9 0
0
0
8 10 0
0
0
0
0
2
| 5
|
Notes
Note that despite the example in the text, Tanya and other employees may call their boss and subordinates in any order.
Problem Author: Eugeniy Krokhalev
Problem Source: IX Collegiate Students Urals Programming Contest. Yekaterinburg, April 19-24, 2005