在這幾天爆發的戰爭中，政府投入大量資源去獲得 VIM 的情報，發現以下幾個資訊：
- VIM 具有龐大的鐵路網路，每個火車站彼此都是雙向連通的。
- 在戰爭爆發之前，每個火車站最多直接連接到另外 10 個火車站。
- VIM 的訊息交換都是藉由鐵路，在戰爭爆發之前，他們都盡可能使用鐵路通訊。
- 為了抵抗戰爭來襲，帝國中央命令可以藉由鴿子來傳遞訊息，但是這將會造成昂貴的負擔。因為鴿子要遠從 Pigeons In Courier Outfits (PICO) 的島嶼進口過來。
- 一旦鴿子抵達其中一個火車站，則就會休息，而且不能再次使用。因此盡可能使用火車來傳輸，而鴿子帶來的訊息將會被鐵路傳輸到其他火車站。
由於這些資訊，EMACS 政府打算擬策計畫來破壞邪惡帝國的活動，他們打算派出轟炸機摧毀火車站，妨礙帝國的訊息通訊，而帝國就必須引入鴿子來協助，藉此分散他們對戰爭的助力。
不幸地， 政府花太多錢在蒐集情報，以至於沒有足夠的錢製作炸彈，於是只能摧毀一個火車站。你要找到最好的候選車站進行催毀，好壞根據 "鴿子值" ，這個鴿子值定義：當一個火車站被摧毀後，中央至少要派幾隻鴿子進行傳輸的工作，才能傳遞到所有未摧毀的火車站
由於不知道中央指揮部在哪，也就是說他們至少一定會使用一個鴿子將訊息傳遞到一個未摧毀的火車站，再經由鐵路傳遞到更遠的火車站。
Input
輸入有多組測資，每組第一行有兩個整數 n, m。
- n：(3 <= n <= 10000) 表示帝國火車站個數，且編號從 0 到 n-1 。
- m：(1 <= m <= n) 表示要挑選候選的個數。
接下來會有數行表示鐵路連接資訊，每行 (x,y)，表示 x 和 y 相連，直到 x = y = -1 表示資訊結束。
當 n = m = 0 結束程式。
Output
對於每組測資，輸出 m 行，輸出候選火車站的資訊，根據鴿子值由高到低，相同時則按照鴿子值由小到大，只要輸出前 m 個即可。每組測資後輸出一行空行。
Sample Input Output for Sample Input
8 4
0 4
1 2
2 3
2 4
3 5
3 6
3 7
6 7
-1 -1
0 0
|
2 3
3 3
4 2
0 1
|
沒有留言:
張貼留言