TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

94.3% (116/123)

Submission's AC Ratio

40.0% (210/525)

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

Sample Output 1

0
0
1
4

Hints

Problem Source

原TIOJ1137 / 96 TWN Practice Contest 1。Problem Setter: Tmt。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1