#include<bits/stdc++.h>

using namespace std;

const int N=;

struct node

{

    int L,R;

}s[N];

int toint(char ch)

{

    if(ch=='-'){

        return -;

    }

    else{

        return ch-'';

    }

}

int isroot[N];

void postorder(int root)

{

    if(root==-){

        return;

    }

    postorder(s[root].L);

    postorder(s[root].R);

    swap(s[root].L,s[root].R);

}

vector<int>in;

void print(int root)

{

    if(root!=-){

        print(s[root].L);

        in.push_back(root);

        print(s[root].R);

    }

}

vector<int>le;

void lever(int root)

{

    queue<int>Q;

    Q.push(root);

    while(!Q.empty()){

        int u=Q.front();

        Q.pop();

        le.push_back(u);

        if(s[u].L!=-) Q.push(s[u].L);

        if(s[u].R!=-) Q.push(s[u].R);

    }

}

int main()

{

    fill(isroot,isroot+N,false);

    int n;

    scanf("%d",&n);

    for(int i=;i<n;i++){

        char ch1,ch2;

        scanf("%*c%c %c",&ch1,&ch2);

        int a=toint(ch1);

        int b=toint(ch2);

        s[i].L=a;

        s[i].R=b;

        isroot[a]=true;

        isroot[b]=true;

    }

    int root=;

    for(int i=;i<n;i++){

        if(isroot[i]==false){

            root=i;

        }

    }

    postorder(root);

    print(root);

    lever(root);

    for(int i=;i<le.size();i++){

        if(i) printf(" ");

        printf("%d",le[i]);

    }

    printf("\n");

    for(int i=;i<in.size();i++){

        if(i) printf(" ");

        printf("%d",in[i]);

    }

    printf("\n");

    return ;

}