a136. P_8_14 血緣關係 (APCS201603)

Content

小宇有一個大家族。有一天，他發現記錄整個家族成員和成員間血緣關係的家族族譜。小宇對於最遠的血緣關係 (我們稱之為"血緣距離") 有多遠感到很好奇。0是7的孩子，1、2和3是0的孩子，4和5是1的孩子，6是3的孩子。我們可以輕易的發現最遠的親戚關係為4(或5)和6，他們的"血緣距離"是4 (4~1，1~0，0~3，3~6)。我們將給你小宇家族的關係圖，請幫小宇找出最遠的"血緣距離"。你可以假設只有一個人是整個家族成員的祖先，而且沒有兩個成員有同樣的小孩。

Input

第一行為一個正整數n 代表成員的個數，每人以0~n-1之間惟一的編號代表。接著的n-1行，每行有兩個以一個空白隔開的整數a與b (0 ≤ a,b ≤ n-1)，代表b是a的孩子。n不超過1e5。

Output

輸出最遠"血緣距離"的答案。

Sample Input #1

範例一輸入：
8
0 1
0 2
0 3
7 0
1 4
1 5
3

範例二輸入：
4
0 1
0 2
2

Sample Output #1

範例一輸出：
4

範例二輸出：
3

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (20%): 1.0s , <10M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

Tags:

ch8

出處:

Prof.Wu [管理者： s710426(?0_o)//) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」