白駿1991号:木巡り

import sys

N = int(input())
BST = {}

for i in range(N):
    pN, lN, rN = sys.stdin.readline().split()
    if i == 0: Root = pN
    BST[pN] = (lN, rN)

def preOrder(data):
    print(data, end="")
    if BST[data][0] != '.':
        preOrder(BST[data][0])
    if BST[data][1] != '.':
        preOrder(BST[data][1])

def inOrder(data):
    if BST[data][0] != '.':
        inOrder(BST[data][0])
    print(data, end="")    
    if BST[data][1] != '.':
        inOrder(BST[data][1])
        
def postOrder(data):
    if BST[data][0] != '.':
        postOrder(BST[data][0])    
    if BST[data][1] != '.':
        postOrder(BST[data][1])
    print(data, end="")
    
preOrder(Root)
print()
inOrder(Root)
print()
postOrder(Root)
print()