# python3
import queue
import sys


def in_order(key, left, right):
    keyIndexStack = []
    result = []
    walkLeft = True

    currentIndex = 0
    keyIndexStack.append(currentIndex)
    while len(keyIndexStack) != 0 or right[currentIndex] != -1:
        if walkLeft:
            if left[currentIndex] != -1:
                currentIndex = left[currentIndex]
                keyIndexStack.append(currentIndex)
            else:
                result.append(key[keyIndexStack.pop()])
                walkLeft = False
        else:
            if right[currentIndex] != -1:
                currentIndex = right[currentIndex]
                keyIndexStack.append(currentIndex)
                walkLeft = True
            else:
                if len(keyIndexStack) != 0:
                    currentIndex = keyIndexStack.pop()
                    result.append(key[currentIndex])
    return result


def pre_order(key, left, right):
    keyIndexStack = []
    keyIndexQueue = queue.Queue()
    result = []

    walkLeft = True
    currentIndex = 0
    keyIndexStack.append(currentIndex)
    keyIndexQueue.put(currentIndex)

    while len(keyIndexStack) != 0 or right[currentIndex] != -1:
        if walkLeft:
            if left[currentIndex] != -1:
                currentIndex = left[currentIndex]
                keyIndexQueue.put(currentIndex)
                keyIndexStack.append(currentIndex)
            else:
                keyIndexStack.pop()
                walkLeft = False
                result.append(key[keyIndexQueue.get()])
        else:
            if right[currentIndex] != -1:
                currentIndex = right[currentIndex]
                keyIndexQueue.put(currentIndex)
                keyIndexStack.append(currentIndex)
                walkLeft = True
            else:
                if len(keyIndexStack) != 0:
                    currentIndex = keyIndexStack.pop()
                    result.append(key[keyIndexQueue.get()])
    return result


def post_order(key, left, right):
    keyIndexStack = []
    peekedSet = set([])
    result = []

    walkLeft = True
    currentIndex = 0
    keyIndexStack.append(currentIndex)
    while len(keyIndexStack) != 0:
        if currentIndex in peekedSet:
            result.append(key[currentIndex])
            peekedSet.remove(currentIndex)
            keyIndexStack.pop()
            if len(keyIndexStack) == 0:
                break
            currentIndex = keyIndexStack[-1]
            continue
        if walkLeft:
            if left[currentIndex] != -1:
                currentIndex = left[currentIndex]
                keyIndexStack.append(currentIndex)
            else:
                if right[currentIndex] == -1:
                    result.append(key[currentIndex])
                    walkLeft = False
                    keyIndexStack.pop()
                    currentIndex = keyIndexStack[-1]
                else:
                    peekedSet.add(currentIndex)
                    currentIndex = right[currentIndex]
                    keyIndexStack.append(currentIndex)
        else:
            if right[currentIndex] != -1:
                peekedSet.add(currentIndex)
                currentIndex = right[currentIndex]
                keyIndexStack.append(currentIndex)
                walkLeft = True
            else:
                result.append(key[currentIndex])
                i = keyIndexStack.pop();
                if i != currentIndex:
                    result.append(key[i])
                if len(keyIndexStack) == 0:
                    break
                currentIndex = keyIndexStack[-1]
    return result


if __name__ == '__main__':
    n = int(sys.stdin.readline())
    key = [0 for i in range(n)]
    left = [0 for i in range(n)]
    right = [0 for i in range(n)]
    for i in range(n):
        [a, b, c] = map(int, sys.stdin.readline().split())
        key[i] = a
        left[i] = b
        right[i] = c
    print(" ".join(str(x) for x in in_order(key, left, right)))
    print(" ".join(str(x) for x in pre_order(key, left, right)))
    print(" ".join(str(x) for x in post_order(key, left, right)))