TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

91.3% (63/69)

Submission's AC Ratio

18.9% (125/661)

Tags

Description

在開始之前,也許你會想要先聽一首歌。

你的朋友,小美,天龍國的資料分析專家,今天也在努力地工作著。
一天,有一個女生來找你和小美,原來他就是果茶的病嬌女友,希佳佳!

事情是這樣的,因為一些複雜的原因,果茶和小希吵了一架之後分手了,可是因為小希是病嬌,所以她沒有這麼容易就放過果茶。
原來,小希早就對果茶喜歡的類型聊若指掌,不管是要不要加分號還是要不要加括號之類的。
她決定變成果茶喜歡的類型,希望果茶回心轉意。

可是事情沒有小希想的那麼順利,不但出現了意外的編譯錯誤之外,被指針亂搞的記憶體也不停的Overflow。
「嗚...!你為什麼習慣就是那麼差呢!不是說了指針戳到陣列外面很危險嗎!!!!」
「還...還不是因為妳不做好安全措施!妳看看人家小啪,陣列怎麼弄都不會溢位!」
「還不是因為你喜歡直接用指針戳記憶體!嗚,而且安全措施本來就是你的責任啦!」
「所以我一開始就說用STL也沒關係啊!」
「你還說,明明就是你用了STL之後還用memset,很痛你知道嗎!」
「算了隨便妳啦,我要去寫網頁了。」
「嗚--你又要去寫那種不管什麼型別都OK的語言了嗎!那種語言到底哪裡好啊!」
「只是工作而已,拜託妳就忍耐一吧。」說完果茶就出門了。
「嗚...」

經過了上面那串意義不明的對話之後,小希認為還有什麼地方不夠,於是來找小美幫她分析一下如何才能成為一個全方位的程式語言。
因為小美曾經聽過小希為了排除所有接近果茶的女人,不但刪光了其他的程式,甚至綁架了果茶的首頁,手段非常凶殘,小美決定趕快解決這個棘手的案子。

「只要知道果茶喜歡的所有條件就可以了吧?」

小希收集的資料經過小美精密的分析之後,小美繪製出了一張圖,上面記錄了各種類型妹子的性質,並且在相關的性質之前用邊連接起來。
為了方便,我們點代表不同的性質,為了分類這些性質,我們將這些性質的關係分成高相關和低相關。
只要兩點在圖上是連通的,我們就稱這兩個性質是相關性值,要知道不管是多麼奇怪的妹子,個性總是會和其他類型有一點相關,也就是這張圖中所有的點都是互相連通的。
然而,假如我們切斷了其中一條邊, 會讓某一個點沒辦法跟其他所有的點都連通,也就是會讓某個性質沒辦法和其他所有性質相關的話 ,我們就稱這條邊是這張圖中的「特殊關係」,而要是一群點之間不存在特殊關係,我們就稱這群點為「高相關」,而兩點間存在特殊關係的話,則稱這兩點為低相關。
我們可以把點分成很多組高相關的點群,這樣就能方便小希了解那些性質之間比較類似,而那些又比較不同。

現在小美已經畫完關係圖了,可是他也有他的妹子要陪,於是他把任務交給了沒有妹子的你,你可以幫助他解決小希的煩惱嗎,也許這樣之後你可以少遇到一些BUG喔。

Input Format

第一行有兩個整數n,m,分別代表有n個點和m條邊。
接下來m行,每行兩個整數a,b,代表a到b之間有一條雙向邊連接。

對於20%的測資:
$ m = n-1 $

對於20%的測資:
$ m = n $
而且每個點的度數不超過2。

對於所有測資:
$ 1 \leq n \leq 10^ 4$
$ 1 \leq m \leq 4 * 10^ 4$
$ 0 \leq a,b < 10^ 4$

Output Format

對於每個高相關的群組,輸出一行,每個數字以一個空白隔開,並依照數字大小排列,每個群組按照開頭的第一個數字大小排列。
格式請參考範例輸出。

Sample Input 1

6 7
0 1
1 2
2 3
3 4
4 5
0 2
3 5

Sample Output 1

1: 0 1 2
2: 3 4 5

Hints

小希回到家看到果茶正在和小結(JS) 還有小啪(Py)玩。
小希非常生氣,一氣之下把你寫的程式當作武器丟向果茶,結果還沒丟到就被防毒軟體刪掉了。
小希:「不用加分號到底哪裡好啦!!!」
小啪:「當然好啦~而且小啪數學也很好呦~不用寫大數呦~」
小結:「人...人家其實也可以加分號的說...。」
果茶今天也在努力奮鬥著...。

Problem Source

果茶
2016建中資訊校隊補選pD

Subtasks

No. Testdata Range Score
1 0~8 60
2 9 20
3 10 20

Testdata and Limits

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