#include <iostream>
#include <vector>

constexpr int MAX_N = 1e5 + 1;

class BinaryTree {
public:
    using NodeIdx = int;

    struct Node {
        NodeIdx father = -1, left = -1, right = -1;
    };

    NodeIdx root = -1;
    std::vector<Node> nodes;

    explicit BinaryTree(int n) : nodes(n) {}

    NodeIdx init_root() {
        root = 0;
        while (nodes[root].father != -1) {
            root = nodes[root].father;
        }
        return root;
    }

    [[nodiscard]] std::vector<int> preorder_traversal() {
        std::vector<int> result;
        result.reserve(nodes.size());
        preorder_dfs(root, result);
        return result;
    }

    [[nodiscard]] std::vector<int> postorder_transversal() {
        std::vector<int> result;
        result.reserve(nodes.size());
        postorder_dfs(root, result);
        return result;
    }

    [[nodiscard]] std::vector<int> inorder_transversal() {
        std::vector<int> result;
        result.reserve(nodes.size());
        inorder_dfs(root, result);
        return result;
    }

protected:
    void preorder_dfs(NodeIdx node, std::vector<int>& result) {
        if (node == -1) { return; }
        result.push_back(node);
        preorder_dfs(nodes[node].left, result);
        preorder_dfs(nodes[node].right, result);
    }

    void postorder_dfs(NodeIdx node, std::vector<int>& result) {
        if (node == -1) { return; }
        postorder_dfs(nodes[node].left, result);
        postorder_dfs(nodes[node].right, result);
        result.push_back(node);
    }

    void inorder_dfs(NodeIdx node, std::vector<int>& result) {
        if (node == -1) { return; }
        inorder_dfs(nodes[node].left, result);
        result.push_back(node);
        inorder_dfs(nodes[node].right, result);
    }
};

std::ostream& operator<<(std::ostream& os, const std::vector<int>& vector) {
    for (int x : vector) { os << x + 1 << ' '; }
    return os;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    BinaryTree binary_tree(n);

    for (int i = 0; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        x--, y--;

        binary_tree.nodes[i].left = x;
        binary_tree.nodes[i].right = y;
        if (x >= 0) { binary_tree.nodes[x].father = i; }
        if (y >= 0) { binary_tree.nodes[y].father = i; }
    }

    binary_tree.init_root();

    std::cout << binary_tree.preorder_traversal() << std::endl;
    std::cout << binary_tree.inorder_transversal() << std::endl;
    std::cout << binary_tree.postorder_transversal() << std::endl;

    return 0;
}