#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
int l[N], r[N], levelorder[N], inorder[N];
int n, index;
bool st[N];

void dfs(int root)
{
    if(l[root] != -1) dfs(l[root]);
    if(r[root] != -1) dfs(r[root]);
    int tmp = l[root];
    l[root] = r[root];
    r[root] = tmp;
}

void dfs_inorder(int root)
{
    if(l[root] != -1) dfs_inorder(l[root]);
    inorder[index ++] = root;
    if(r[root] != -1) dfs_inorder(r[root]);
}

void dfs_levelorder(int root)
{
    int hh = 0, tt = 0;
    levelorder[++ tt] = root;
    while(tt > hh)
    {
        int t = levelorder[++ hh];
        if(l[t] != -1) levelorder[++ tt] = l[t];
        if(r[t] != -1) levelorder[++ tt] = r[t];
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        char ch1, ch2;
        cin >> ch1 >> ch2;
        if(ch1 != '-') l[i] = ch1 - '0', st[l[i]] = true;
        else if(ch1 == '-') l[i] = -1;
        if(ch2 != '-') r[i] = ch2 - '0', st[r[i]] = true;
        else if(ch2 == '-') r[i] = -1;
    }
    int root = 0;
    while(st[root]) root ++;  //找到根节点
    dfs(root);
    dfs_inorder(root);
    index = 0;
    dfs_levelorder(root);
    cout << levelorder[1];
    for(int i = 2; i <= n; i ++) cout << " " << levelorder[i];
    cout << endl;
    cout << inorder[0];
    for(int i = 1; i < n; i ++) cout << " " << inorder[i];
    return 0;
}
要记得给没有孩子结点的标志为-1