1152 . 1.銀河帝國旅行社
TopCoder
Description
如果想要忠於原味可以從這裡找到題目：
http://www.cs.nthu.edu.tw/info_race93/93problem-f.pdf
很久很久以前，銀河系有一個科技極度發達的帝國存在，這個帝國有著許許多多的星球所組成，這些星球之間有主從關係，除了帝國首都之外，其他的星球均從屬於自己專屬的主星。
由於銀河是相當的浩瀚，主要的旅行方式是空間跳躍，不管這兩個星球有多遠只要花一小時就抵達目的地。為了維護帝國間的和平與安定，帝國當局是嚴格的管制空間跳躍的使用，只允許主星到從屬星以及從屬星到主星之間的的空間跳躍。假定銀河帝國中，只有一個帝國首都，首都本身也是一個星球，每個星球只有一個專屬的主星，但一個星球可以有許多從屬星。並且不會發生循環從屬的關係，即不會發生如下情況：S1是S2的主星，S2是S3的主星...Sn-1是Sn的主星，Sn是S1的主星。
以下圖為例，1號星與2號星為0號星(也就是帝國首都)的從屬星，3號星是1號星的從屬星，4號星是2號星的從屬星。在這個例子中，從3號星到2號星作星際旅行需要3小時：3號星 → 1號星，1號星 → 0號星，0號星 → 2號星。而在這個星系中作星際旅行，最多需要花4小時，也就是從3號星旅行到4號星。
現在你的任務是估計銀河帝國之中，任意選兩個星球作為起點與終點進行空間跳躍旅行，最多需要花多少時間？(以上圖為例，答案是4個小時。)
Input Format
第一行將有一個數字n (n<=10000)，代表了銀河帝國中有 n個星球。緊接下來會有 n行，接下來的每行依序都代表了一個星球的從屬星名單。為了簡化輸入的複雜度，將由0到 n-1 的數字來替代星球名稱，0就是帝國首都，而且只有數字小的才可以當數字大的主星。每行的格式："從屬星1 從屬星2 … -1"，最後的-1代表從屬星名單結束，如果是單一一行的-1，代表該星球沒有從屬星。
Output Format
輸出一行，包含一個數字。即任選兩個星球，最多需要花多少小時才能藉由空間跳躍從起點到達目的地。
Sample Input 1
1 2 -1
3 -1
4 -1
-1
-1
Sample Output 1
Sample Input 2
1 -1
2 3 4 5 -1
-1
-1
-1
-1
Sample Output 2
Hints
Problem Source
原TIOJ1152 / 93全國賽(prob 1)。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 33 |
| 2 | 1 | 33 |
| 3 | 2 | 34 |