#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct treee{
    int l,r;
}tree[N];
int n;
void a(int x){
    cout<<x<<" ";
    if(tree[x].l){
        a(tree[x].l);
    }
    if(tree[x].r){
        a(tree[x].r);
    }
}
void b(int x){
    if(tree[x].l){
        b(tree[x].l);
    }
    cout<<x<<" ";
    if(tree[x].r){
        b(tree[x].r);
    }
}
void c(int x){
    if(tree[x].l){
        c(tree[x].l);
    }
    if(tree[x].r){
        c(tree[x].r);
    }
    cout<<x<<" ";
}
int main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        tree[i].l=u;
        tree[i].r=v;
    }
    a(1);
    cout<<"\n";
    b(1);
    cout<<"\n";
    c(1);
    return 0;
}