思路：ACM赛制下就需要手搓一棵符合题目要求的二叉树了，没有接触过的同学可以练习一下，具体流程如下：1.写一个节点类；2.分别对各编号建立节点；3.读入边然后建二叉树，顺便存储一下边；4.通过入度为0，找到根节点编号，并取出根；5.用经典的递归来写三种遍历方式，输出结果即可，当然你也可以扩展一下，用非递归的栈来写

代码；

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def solve():
    n = II()

    edge = []
    nodes = [None] * (n + 1)
    for i in range(1, n + 1):
        nodes[i] = Node(i)

    for _ in range(n - 1):
        a, b = MII()
        edge.append((a, b))
        par, son = nodes[a], nodes[b]
        if not par.left:
            par.left = son
        else:
            if not par.right:
                if par.left.val < son.val:
                    par.right = son
                else:
                    par.right = par.left
                    par.left = son

    deg = [0] * (n + 1)
    for i in range(n - 1):
        a, b = edge[i]
        deg[b] += 1
    root_idx = next(i for i in range(1, n + 1) if deg[i] == 0)
    root = nodes[root_idx]

    def pre(root):
        if not root:
            return
        print(root.val, end=" ")
        pre(root.left)
        pre(root.right)

    def mid(root):
        if not root:
            return
        mid(root.left)
        print(root.val, end=" ")
        mid(root.right)

    def suf(root):
        if not root:
            return
        suf(root.left)
        suf(root.right)
        print(root.val, end=" ")

    pre(root)
    print()
    mid(root)
    print()
    suf(root)

t = 1
# t = II()
for _ in range(t):
    solve()