TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

90.0% (36/40)

Submission's AC Ratio

49.7% (85/171)

Description

給你兩棵樹,請問這兩棵樹是否同構?
所謂同構的意思,就是把它們畫在紙上的時候,存在一種畫法能夠讓兩棵樹看起來一樣(編號可能不同,但是結構一樣)。

Input Format

輸入檔可能包含多筆測試資料。
每筆測試資料的第一列有一個正整數n(1<=n<=100),接下來2n-2列每列有兩個正整數i,j(1<=i,j<=n)。
前n-1列代表第一棵樹,後n-1列代表另外一棵樹。兩棵樹的節點編號都是從1編號到n。
當n=0時代表輸入結束。你可以假設輸入的測試資料都是合理的。

Output Format

對於每筆測試資料,如果兩棵樹同構,請輸出Same,否則請輸出Different。

Sample Input

5
1 2
2 3
2 4
4 5
1 3
2 5
3 5
4 5
5
1 2
2 3
2 4
4 5
1 2
2 3
2 4
2 5
0

Sample Output

Same
Different

Hints

Problem Source

原TIOJ1214 / TIOJ 2008例行賽03 (prob F)。經典問題練習。Problem Setter:Tmt。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1