TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

98.7% (76/77)

Submission's AC Ratio

64.0% (169/264)

Tags

Description

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

Input Format

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

Output Format

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

Sample Input 1

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 1

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

Hints

Problem Source

原TIOJ1256 / INFOR 21st幹部考(prob L)。Problem Setter:peter50216。
2021.03.30 Update: Added $\LaTeX$ by FHVirus

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 (VSS, 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