ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1362. Classmates 2

Time limit: 2.0 second
Memory limit: 64 MB
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.


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 consists of one number — the minimum time, in minutes, that is required to propagate Tanya's idea to all ACM employees.


2 3 0
4 5 7 0
6 9 0
8 10 0


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