TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

82.6% (19/23)

Submission's AC Ratio

47.1% (56/119)

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

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144