1444 . 郵局設置問題
TopCoder
Tags
Description
你知道郵差的辛苦嗎？
冒著風吹雨淋只為了替人們送達那名為信件的感動。
所以為了體恤郵差們的辛勞，郵局設置的位置成了一個重要的問題。
在一個世外桃源中，有一個名叫真新鎮的純樸小鎮，居民們快樂地生活在那裡。
不過由於過於安逸，為了避免麻煩，每個居民到另外一名居民的家只有一條路徑，而每戶人家的間隔距離也是固定的。
雖然日子很悠閒，但由於小鎮過於龐大，卻又缺少郵局，所以每次信件都要仰賴隔壁鎮的郵差幫忙，讓人十分苦惱。
你是一個真新鎮的鎮長小智，正準備在鎮上的某一個人家裡設置一個郵局（居民們都很樂意將自己家裡變成郵局，因為這是偉大的貢獻）
但為了郵差的辛勞，所以你想要盡量讓郵差從郵局到最遠的一戶人家家裡的距離最短（假設每戶人家的間隔距離為1）。
另外，你還想知道會使得從郵局到最遠的一戶人家家裡的距離最遠的地點是哪裡，好知道哪裡絕對不能設置郵局。
Input Format
本題只有一筆測試資料：
第一行包含兩個正整數 $n, m$ ，代表小鎮裡戶數以及小鎮的道路數
（$0 < n \leq 5000$，$m$ 則會在合理範圍內）
接下來有 $m$ 行，
每行有兩個數字 $a, b$，代表 $a$ 居民的家與 $b$ 居民的家之間有一條單位長為 $1$ 的道路連接
（$1 \leq a, b \leq n$）
Output Format
第一行請輸出選擇哪些居民的家當作郵局最好（按照編號由小到大輸出）
第二行請輸出選擇哪些居民的家當作郵局最不好（按照編號由小到大輸出）
Sample Input 1
1 2
1 3
2 6
2 7
3 4
3 5
Sample Output 1
4 5 6 7
Hints
※2008/10/08 測資範圍加入 by hallogameboy，感謝 peter50216。
※2008/10/08 測資範圍更改 by hallogameboy。
※2021/02/14 Added $\LaTeX$ by FHVirus
Problem Source
原TIOJ1444 / 建中校內培訓第一次模擬考試。
Problem Setter：hallogameboy、peter50216
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |