#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int l, r, fa;
} a[1000001];

inline void preorder(int i) {
    printf("%d ", i);
    if (a[i].l)
        preorder(a[i].l);
    if (a[i].r)
        preorder(a[i].r);
}

inline void inorder(int i) {
    if (a[i].l)
        inorder(a[i].l);
    printf("%d ", i);
    if (a[i].r)
        inorder(a[i].r);
}

inline void postorder(int i) {
    if (a[i].l)
        postorder(a[i].l);
    if (a[i].r)
        postorder(a[i].r);
    printf("%d ", i);
}

int n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x) 
            a[i].l = x, a[x].fa = i;
        if (y)
            a[i].r = y, a[y].fa = i;
    }
    preorder(1);
    printf("\n");
    inorder(1);
    printf("\n");
    postorder(1);
    printf("\n");

    return 0;
}