#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int val = 0, TreeNode *left = nullptr, TreeNode *right = nullptr) : val(val), left(left), right(right) {}
};
void preorder(TreeNode *root) {
    if (root == nullptr) return ;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
    return ;
}
void inorder(TreeNode *root) {
    if (root == nullptr) return ;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
    return ;
}
void lastorder(TreeNode *root) {
    if (root == nullptr) return ;
    lastorder(root->left);
    lastorder(root->right);
    cout << root->val << " ";
    return ;
}
TreeNode *a[20];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++) {
    	cout << "i = " << i << endl;
        a[i]->val = i;
        cout << "val赋值完成\n";
		a[i]->left = a[i]->right = nullptr;
	}
    cout << "赋值完成\n";
    for (int i = 0; i < n; i++) {
        int L, R;
        cin >> L >> R;
        a[i]->left = a[L];
        a[i]->right = a[R];
    }
    cout << "更改完成" <<endl;
    TreeNode *root = a[1];
    preorder(root);
    puts("");
    inorder(root);
    puts("");
    lastorder(root);
    return 0;
}