1137 . 4.收費站設置問題
TopCoder
Tags
Description
蕃茄國有n個城市以及m條雙向道路連接這n個城市，並且任何兩個城市之間都至少有一條路可以到達。
由於國家財政上的困難，蕃茄國的行政部門想要在這些城市當中選一些城市設置收費站，而這些被選中的城市滿足：
至少有除了被選中城市以外的兩個城市，其所有連接該二城市的路徑都必須經過被選中的城市。
現在給你蕃茄國的地圖，請問有多少個城市可以設置收費站呢？
Input Format
輸入檔的第一列有一個正整數T，代表接下來測試資料的筆數。
每筆測試資料的第一列有兩個正整數n,m，代表有n個城市(城市編號為1,2,...,n），m條雙向道路。
然後的m列每列有兩個正整數Ai,Bi(1<=Ai,Bi<=n)，代表第i條道路連接Ai以及Bi兩個城市。
(1<=n<=10,000, 1<=m<=100,000)
Output Format
對於每筆測試資料請輸出兩列：第一列輸出能夠設置收費站的城市總數，第二列由小到大輸出能夠設置收費站城市的編號，
如果沒辦法設置任何收費站，第二列請輸出0。
Sample Input 1
2
3 3
1 2
2 3
3 1
5 5
1 2
2 3
3 4
4 5
1 4
3 3
1 2
2 3
3 1
5 5
1 2
2 3
3 4
4 5
1 4
Sample Output 1
0
0
1
4
0
1
4
Hints
Problem Source
原TIOJ1137 / 96 TWN Practice Contest 1。Problem Setter: Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |