TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

『觸手(學名:tentacle)是一種生物體上的器官或稱觸鬚、觸角,常見於軟體動物,
    通常是複數,從數根到無法計量之數目的蠕動柔軟細長器官。大多用作感測外界環境變化,但觸手也可用來攫取物體。』

(觸手美妙的地方族繁不及輩載,只是礙於題目篇幅先讓大家對觸手有個大概的了解)

自ieml帶領的研究團隊研發出TDX-107型觸手後,生長期大幅縮短的觸手大大降低了生產成本,並且原先具攻擊性、繁殖力過強的問題都被改善(此型的觸手必須利用人工複製技術才能繁殖),使得觸手這種人造生物成為家庭寵物的熱門選擇。

然而,對於觸手的飼主來說,麻煩的卻是餵食,觸手的觸手就像大蟒蛇的身身體一樣,是無法拾取細微的東西的,所以,觸手的主人為了不讓可愛的觸手挨餓,每次餵食必須找到觸手的頭部,然後再餵食觸手飼料。

身為曉癸觸手專賣店的老闆ーー曉癸,每天總是為了找到他養的每隻觸手的頭部傷腦筋,甚至,觸手常常纏在一起,導致他很難知道說這團觸手究竟有幾隻觸手,所以他請你開發一個觸手自動餵食程式。如果你能達到他的要求,說不定他會送你一隻觸手當作謝禮喔!

一隻觸手的身體結構是一個頭部,以這個頭部為中心長出很多根觸手,然後,這些觸手上面每隔一段長度會有生長點,生長點有可能再長出分支觸手,對了,觸手的末端也會是生長點(這樣才能讓觸手再長長),且頭部也是一個生長點,並且長得跟其他生長點一模一樣(可是牠就是要用頭部進食,神奇吧!)。

我們定義不平衡度為頭部到所有生長點的距離平方和。

一個觸手自動餵食程式需要有以下功能:
  -讀入一坨觸手的生長點以及連接情形
  -分析這坨觸手有幾隻觸手
  -分別找出每隻觸手跟其頭部和體重

PS:觸手的體重是生長點的數目

Input Format

一坨觸手的描述。

第一行有空白隔開的兩個正整數 N, M (1≦N,M≦106),代表有 N 個生長點跟 M 段連接組織。

接下來有M行,有用空白隔開的兩個數 a, b(0≦a,b<N),表示該段組織連接了a, b 兩個生長點。

Output Format

如果你找到了K隻觸手,就輸K行。

每行輸出該觸手的頭部以及體重,用空白隔開。

請照觸手的頭部編號順序輸出。

如果有多個頭部請以編號最小的當頭。

Sample Input

4 3
0 1
1 2
1 3

Sample Output

1 4

Hints

※ Memory Limit 放寬 - skyly 01/02

Problem Source

原TIOJ1592 / Problem Setter: butterfly21

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 2000 131072 262144 1
1 2000 131072 262144 2
2 2000 131072 262144 3
3 2000 131072 262144 4
4 2000 131072 262144 5
5 2000 131072 262144 6
6 2000 131072 262144 7
7 2000 131072 262144 8
8 2000 131072 262144 9
9 2000 131072 262144 10