User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

21.3% (13/61)

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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 4000 65536 262144
1 4000 65536 262144
2 4000 65536 262144
3 4000 65536 262144
4 4000 65536 262144
5 4000 65536 262144
6 4000 65536 262144
7 4000 65536 262144
8 4000 65536 262144
9 4000 65536 262144