User's AC Ratio

100.0% (44/44)

Submission's AC Ratio

85.3% (64/75)

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

Sample Input #1:
5
1 2 -1
3 -1
4 -1
-1
-1

Sample Input #2:
6
1 -1
2 3 4 5 -1
-1
-1
-1
-1

Sample Output

Sample Output #1:
4

Sample Output #2:
2

Hints

Problem Source

原TIOJ1152 / 93全國賽(prob 1)。

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 65536 262144
1 900 65536 262144
2 900 65536 262144