『觸手(學名:tentacle)是一種生物體上的器官或稱觸鬚、觸角,常見於軟體動物,
通常是複數,從數根到無法計量之數目的蠕動柔軟細長器官。大多用作感測外界環境變化,但觸手也可用來攫取物體。』
(觸手美妙的地方族繁不及輩載,只是礙於題目篇幅先讓大家對觸手有個大概的了解)
自ieml帶領的研究團隊研發出TDX-107型觸手後,生長期大幅縮短的觸手大大降低了生產成本,並且原先具攻擊性、繁殖力過強的問題都被改善(此型的觸手必須利用人工複製技術才能繁殖),使得觸手這種人造生物成為家庭寵物的熱門選擇。
然而,對於觸手的飼主來說,麻煩的卻是餵食,觸手的觸手就像大蟒蛇的身身體一樣,是無法拾取細微的東西的,所以,觸手的主人為了不讓可愛的觸手挨餓,每次餵食必須找到觸手的頭部,然後再餵食觸手飼料。
身為曉癸觸手專賣店的老闆ーー曉癸,每天總是為了找到他養的每隻觸手的頭部傷腦筋,甚至,觸手常常纏在一起,導致他很難知道說這團觸手究竟有幾隻觸手,所以他請你開發一個觸手自動餵食程式。如果你能達到他的要求,說不定他會送你一隻觸手當作謝禮喔!
一隻觸手的身體結構是一個頭部,以這個頭部為中心長出很多根觸手,然後,這些觸手上面每隔一段長度會有生長點,生長點有可能再長出分支觸手,對了,觸手的末端也會是生長點(這樣才能讓觸手再長長),且頭部也是一個生長點,並且長得跟其他生長點一模一樣(可是牠就是要用頭部進食,神奇吧!)。
我們定義不平衡度為頭部到所有生長點的距離平方和。
一個觸手自動餵食程式需要有以下功能:
-讀入一坨觸手的生長點以及連接情形
-分析這坨觸手有幾隻觸手
-分別找出每隻觸手跟其頭部和體重
PS:觸手的體重是生長點的數目。
一坨觸手的描述。
第一行有空白隔開的兩個正整數 N, M (1≦N,M≦106),代表有 N 個生長點跟 M 段連接組織。
接下來有M行,有用空白隔開的兩個數 a, b(0≦a,b<N),表示該段組織連接了a, b 兩個生長點。
如果你找到了K隻觸手,就輸K行。
每行輸出該觸手的頭部以及體重,用空白隔開。
請照觸手的頭部編號順序輸出。
如果有多個頭部請以編號最小的當頭。
※ Memory Limit 放寬 - skyly 01/02
原TIOJ1592 / Problem Setter: butterfly21
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 |