#include <iostream>
using namespace std;

int k;

struct Tree {
    int left,right;
}myTree[17];

void qianxu(int q) {
    //root -> leftson -> rightson
    if(q) {
        cout<<q<<" ";
        qianxu(myTree[q].left);
        qianxu(myTree[q].right); 
    } 
}

void zhongxu(int z) {
    //leftson -> root -> rightson
    if(z) {
        zhongxu(myTree[z].left);
        cout<<z<<" ";
        zhongxu(myTree[z].right);
    }
}

void houxu(int h) {
    //leftson -> rightson -> root
    if(h) {
        houxu(myTree[h].left);
        houxu(myTree[h].right);
        cout<<h<<" ";
    }
}

int main() {
    cin>>k;
    for(int i=1;i<=k;i++) {
        cin>>myTree[i].left>>myTree[i].right;
    }

    qianxu(1);
    cout<<endl;
    zhongxu(1);
    cout<<endl; 
    houxu(1);

    return 0;
}