#include <bits/stdc++.h>
using namespace std;
struct xxx{
    int lc,rc;
}tr[110000];
vector<int> a,b,c;
int n;
void qian(int n)
{
    a.push_back(n);
    if(tr[n].lc!=0)qian(tr[n].lc);
    if(tr[n].rc!=0)qian(tr[n].rc);
}
void zhong(int n)
{
    if(tr[n].lc!=0)qian(tr[n].lc);
    b.push_back(n);
    if(tr[n].rc!=0)qian(tr[n].rc);
}
void hou(int n)
{
    if(tr[n].lc!=0)qian(tr[n].lc);
    if(tr[n].rc!=0)qian(tr[n].rc);
    c.push_back(n);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        tr[i].lc=l;
        tr[i].rc=r;
    }
    qian(1);
    zhong(1);
    hou(1);
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<b[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<=n;i++)
    {
        cout<<c[i]<<" ";
    }
    return 0;
}