TopCoder

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

31.6% (6/19)

Description

最近化學課在上IUPAC烷類命名方法,但是lachu學的不太好,常常會算錯,可是lachu又是化學小老師,這樣太丟臉了,所以請聰明的你幫他寫一個程式,幫助他把烷類命名。

命名方法如下:
一堆碳的結構中,要找出最長的一條碳鏈,作為主鍊。例(氫就省略了):

這樣最長的一條碳鏈長度是8。有兩條支鏈,有一個碳,稱做C1。如果支鏈上有兩個碳就叫做C2,以此類推,十個碳叫做C10。

我們要做的就是幫lachu找出主鏈長度還有每種官能基的個數。

Input Format

輸入可能包含多筆測試資料。
每筆測試資料的第一行有一個正整數N,表示碳的個數(1 ≦ N ≦ 62)。
接下來的N-1行,每行有兩個編號,代表哪個碳和哪個碳之間有單鍵。(每個碳可以連接不限個數個碳)(編號依序為A、B、C......Z、a、b、c......z、0、1、2、3......9,並且一定是由A開始編號)。
當N = 0時,代表輸入結束,聰明的你當然不會對它輸出任何資料。

Output Format

第一行輸出主鏈的長度。
接下來的幾行輸出各種官能基的名稱及個數,由碳數從小到大排序。如果該種官能基的數量為0,就不用輸出。如果沒有任何的官能基,請輸出"No functional group"。
你可以假設最長碳鏈是唯一的,整個碳鏈是連通的並且沒有迴圈。
輸出格式請參考範例測資

Sample Input

6
A C
C E
D B
B C
F E
0

Sample Output

5
C1:1

Hints

(為了版面美觀,這裏使用全形的英文字母,但輸入一律為半形英文字母)

Problem Source

原TIOJ1245 / INFOR 21st幹部考(prob A)。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