TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

97.7% (42/43)

Submission's AC Ratio

64.0% (121/189)

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

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10