#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
int fa[N];//用来存储父节点
int son[2][N];
//用来存储左右孩子，一维存储左还是右，二位存储该结点的值；


void pre(int root){
    if(root == 0)   return;//结点值为0，说明该节点为空，回退；
    cout<<root<<" ";
    pre(son[0][root]);//访问完root开始访问左右孩子
    pre(son[1][root]);
}

void in(int root ){
    if(root == 0 )  return;
    in(son[0][root]);
    cout<<root<<" ";
    in(son[1][root]);
}

void post(int root){
    if(root == 0 )  return;
    post(son[0][root]);
    post(son[1][root]);
    cout<<root<<" ";
}


int main(){
    int n;
    cin>>n;

//由于第i行的l和r表示i的左右孩子，按照输入顺序建树
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        fa[l]=i,fa[r]=i;
        son[0][i]=l,son[1][i]=r;
    }

    pre(1);
    cout<<endl;
    in(1);
    cout<<endl;
    post(1);

}