#include<bits/stdc++.h>
using namespace std;
int n;
struct tree_point {
    int l,r;
}a[100005];
void dfs1(int pos) {
    cout << pos << " ";
    if(pos*2<=100000 && a[pos].l != 0) dfs1(a[pos].l);
    if(pos*2+1<=100000 && a[pos].r != 0) dfs1(a[pos].r);
}
void dfs2(int pos) {
    if(pos*2<=100000 && a[pos].l != 0) dfs2(a[pos].l);
    cout << pos << " ";
    if(pos*2+1<=100000 && a[pos].r != 0) dfs2(a[pos].r);
}
void dfs3(int pos) {
    if(pos*2<=100000 && a[pos].l != 0) dfs3(a[pos].l);
    if(pos*2+1<=100000 && a[pos].r != 0) dfs3(a[pos].r);
    cout << pos << " ";
}
int main() {
    cin >> n;
    for(int i = 1;i<=n;i++) {
        int left,right;
        cin >> left >> right;
        a[i].l = left;
        a[i].r = right;
    }
    dfs1(1);cout << endl;
    dfs2(1);cout << endl;
    dfs3(1);cout << endl;
}