TopCoder

User's AC Ratio

80.0% (8/10)

Submission's AC Ratio

14.3% (16/112)

Description

欸西國有n個城市,彼此之間皆有路相通,但這相通的路徑也是唯一的。

今天為了促進民間學術交流,增進居民感情,欸西國政府決定舉辦一場全國性的ACM大賽, 欸西國狂熱的君主卡恩則決定所有城市的居民都需參與此一活動,否則不但要剔除國籍,還要被卡恩親自處以電桌球電一百場的極刑。

總之,現在問題來了。由於經費限制,欸西國只能選擇其中k(k<=n)個城市作為考場,不位在考場的居民則要就近選擇鄰近的考場並前往參加比賽。

卡恩雖然對不肯參加比賽的人絲毫不留情,其實卻還是很體貼廣大老百姓的。他希望能安排這k個賽場,使得「任一城市的居民到達最近考場的距離之最大值」最小。

給定欸西國的地圖(即城市相連情況)以及k,試問在最妥善的安排下,任一城市到達最臨近考場的距離中之最大值最小為何?

Input Format

第一列有三個整數n, m, k,其中n代表城市數量,m代表道路數量。
城市的編號為1到n。

接下來的m列每列有兩個正整數Ai, Bi,代表第i條道路連接城市i和城市Bi。
(1<=Ai, Bi<=n)

Output Format

請輸出任一城市居民到達最近考場距離最大值的最小值。

Sample Input

範例輸入1
5 4 2
1 2
2 3
3 4
4 5

範例輸入2
5 4 1
1 2
1 3
1 4
4 5

Sample Output

範例輸出1
1

範例輸出2
2

Hints

至少有30%的測試資料中,n不超過20。
至少有40%的測試資料中,欸西國的所有城市連成了一條直線。
至少有60%的測試資料中,n不超過5,000。
對於所有測試資料而言,n不超過1,000,000。

Problem Source

原TIOJ1575 / 97建中校內資訊能力競賽(prob6)

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 4000 65536 262144 1
1 4000 65536 262144 2
2 4000 65536 262144 3
3 4000 65536 262144 4
4 4000 65536 262144 5
5 4000 65536 262144 6
6 4000 65536 262144 7
7 4000 65536 262144 8
8 4000 65536 262144 9
9 4000 65536 262144 10