TopCoder

User's AC Ratio

100.0% (18/18)

Submission's AC Ratio

63.8% (83/130)

Description

好不容易闖過了多道困難的關卡,終點就在眼前了,沒想到前方又突然出現了許多的皮皮擋住去路。這次皮皮不再是存在於棋盤上,而是聚成一團,並且許多皮皮之間會手牽著手(不要懷疑,皮皮會變形術,要有幾隻手就有幾隻手)。
皮皮只要牽手就可以進行能量交流,並且自由聚集力量,而你發現,若場上有N隻皮皮,只要聚集N-1之皮皮的力量,就可以抵禦包含強者物質在內的任何攻擊,現在Jimmy提供了一個外掛程式,可以直接抹殺掉一隻皮皮,但是因為你只有試用版(正式版要錢啊!),只能使用一次,請問哪幾隻皮皮一旦被你抹殺掉之後,你就可以殲滅他們了?

Input Format

輸入可能包含多筆測試資料。每筆測試資料的第一行有兩個正整數 N, M代表皮皮的個數和握手對數(1 ≦ N ≦ 10,000,1 ≦ M ≦ 100,000)。
接下來的M行每行有兩個正整數A, B,表示編號A和編號B的皮皮有牽手。(1 ≦ A, B ≦ N)
當N = M = 0時,代表輸入結束,聰明的你當然不會對它輸出任何資料。

Output Format

請先輸出"Case #N:"表示這是第N筆輸出。
接著請輸出有幾個皮皮是可以被消滅的,並且由小到大輸出他們的編號,如果沒有皮皮被消滅後可以分裂他們的話,請輸出0。

Sample Input

3 3
1 2
2 3
3 1
5 5
1 2
2 3
3 4
4 5
1 4
4 3
1 2
2 3
3 4
0 0

Sample Output

Case #1:0 0
Case #2:1 4
Case #3:2 2 3

Hints

Problem Source

原TIOJ1256 / INFOR 21st幹部考(prob L)。Problem Setter:peter50216。

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 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144