TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

在一個城市裡有N間房子,房子與房子之間有道路相連。任何兩棟房子之間都可以經過某些道路互相往來,而在不重複經過某些路段的情形下,這條路線也是唯一的。換句話說,若把房子看成點,道路看成邊,那麼整個圖形成了一棵樹。


編號為1的房子其實是一間郵局。裡面有兩位郵差每天辛苦地遞送信件到這個城市裡所有的房子。由於郵差們相當地辛苦,他們想要規劃遞送郵件的路線,使得每一天每一棟房子至少有一名郵差送信抵達,而且最後一封信被送出的時間越早越好。


已知郵差們送信時,經過每一段道路的時間恰好都是一分鐘,而且投遞信件到房子裡的時間可以忽略。你能夠幫他們找出最佳路線中,最後一封信抵達的時間嗎?假設兩位郵差在第0分鐘這個時刻同時出發的。

Input Format

輸入可能包含多筆測試資料。每一筆測試資料的第一列有一個正整數N (1<=N<=3000)代表有N間房子。接下來的N-1列每一列有兩個正整數A, B (1<=A, B<=N)代表有一條道路連接A, B這兩間房子,所有的輸入都是合法的,並且輸入以EOF結束。

Output Format

對於每一筆測試資料,請輸出最佳路線中,最後一封信抵達的時間(以分鐘為單位)。

Sample Input 1

6
1 2
2 3
5 2
3 4
6 1

Sample Output 1

4

Hints

Problem Source

Migrated from old NTUJ.

POI ONTAK2009 day2 prob2

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 20000 65536 200