小宇有一個大家族。有一天,他發現記錄整個家族成員和成員間血緣關係的家族族譜。
小宇對於最遠的血緣關係 (我們稱之為"血緣距離") 有多遠感到很好奇。
下圖為家族的關係圖。
0 是 7 的孩子, 1、2 和 3 是 0 的孩子, 4 和 5 是 1 的孩子, 6 是 3 的孩子。
我們可以輕易的發現最遠的親戚關係為 4(或 5) 和 6 ,他們的"血緣距離"是 4 (4→1→0→3→6)。
給予任一家族的關係圖,請找出最遠的"血緣距離"。
你可以假設只有一個人是整個家族成員的祖先,而且沒有兩個成員有同樣的小孩。
輸入包含多筆測資。
每筆側資中,
第一行為一個正整數 N 代表成員的個數,每人以 0~N-1 之間唯一的編號代表。
接著的 N-1 行,每行有兩個以一個空白隔開的整數 a 與 b (0 ≤ a, b ≤ N-1),代表 b 是 a 的孩子。
其中 10%的測資滿足, 2 ≤ N ≤ 100 ,整個家族的祖先最多 2 個小孩,其他成員最多一個小孩。
其中 40%的測資滿足, 2 ≤ N ≤ 100。
其中 70%的測資滿足, 2 ≤ N ≤ 2000。
其中100%的測資滿足, 2 ≤ N ≤ 100000。
每筆測資輸出一行,輸出最遠"血緣距離"的答案。
本題為嚴格比對,請務必按照說明進行輸出。
8 0 1 0 2 0 3 7 0 1 4 1 5 3 6 4 0 1 0 2 2 3
4 3
第一筆說明:如題目所附之圖,最遠路徑為 4→1→0→3→6 或 5→1→0→3→6,距離為 4 。
第二筆說明:最遠路徑為 1→0→2→3,距離為 3 。
ID | User | Problem | Subject | Hit | Post Date |
35419 |
|
b967 | 44 | 2023-06-01 11:54 | |
35241 |
|
b967 | 122 | 2023-05-18 15:30 | |
33453 |
|
b967 | 400 | 2023-01-06 20:09 | |
30043 |
|
b967 | 954 | 2022-04-24 09:17 | |
25613 | fire5386(Penguin07) | b967 | 2029 | 2021-06-06 22:09 |