Problem 1064 --普通樹轉二元樹

1064: 普通樹轉二元樹

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 0
[Submit][Status][Web Board]

Description

輸入一棵普通有序樹,輸出該樹的先根次序和後根次序。

Input

第一行為頂點個數n(1≤n≤26)。以下含n行,其中第i行(1≤i≤n)的元素依次為結點i的數據值ai(為一個小寫字母)。以後各元素為結點i的兒子序列,以0結束。若ai後僅含一個0,則說明結點i為葉子。

Output

輸出共兩行,第一行該樹的前序遍歷,第二行為後序遍歷,節點間沒有空格

Sample Input

18
r 2 3 4 0
a 5 6 0
b 7 0
c 8 9 10 0
w 0
x 11 12 0
f 0
s 13 14 0
t 0
u 0
d 15 0
e 0
i 16 17 18 0
j 0
h 0
m 0
o 0
n 0

Sample Output

rawxdhebfcsimonjtu
hedxwfnomjiutscbar

HINT

Source

[Submit][Status]