import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class TreeTraversal {
    static class FastScanner {
        StringTokenizer tok = new StringTokenizer("");
        BufferedReader in;

        FastScanner() {
            in = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (!tok.hasMoreElements())
                tok = new StringTokenizer(in.readLine());
            return tok.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

    static class TreeOrders {
        int n;
        int[] key, left, right;

        void read() throws IOException {
            FastScanner in = new FastScanner();
            n = in.nextInt();
            key = new int[n];
            left = new int[n];
            right = new int[n];
            for (int i = 0; i < n; i++) {
                key[i] = in.nextInt();
                left[i] = in.nextInt();
                right[i] = in.nextInt();
            }
        }

        List<Integer> inOrder() {
            Stack<Integer> keyIndexStack = new Stack<>();
            ArrayList<Integer> result = new ArrayList<>();
            // Finish the implementation
            // You may need to add a new recursive method to do that
            boolean walkLeft = true;
            int currentIndex = 0;
            keyIndexStack.push(currentIndex);
            while (!keyIndexStack.empty() || right[currentIndex] != -1) {
                if (walkLeft) {
                    if (left[currentIndex] != -1) {
                        currentIndex = left[currentIndex];
                        keyIndexStack.push(currentIndex);
                    } else {
                        result.add(key[keyIndexStack.pop()]);
                        walkLeft = false;
                    }
                } else {
                    if (right[currentIndex] != -1) {
                        currentIndex = right[currentIndex];
                        keyIndexStack.push(currentIndex);
                        walkLeft = true;
                    } else {
                        if (!keyIndexStack.empty()) {
                            currentIndex = keyIndexStack.pop();
                            result.add(key[currentIndex]);
                        }
                    }
                }
            }
            return result;
        }

        List<Integer> preOrder() {
            Stack<Integer> keyIndexStack = new Stack<>();
            Queue<Integer> keyIndexQueue = new LinkedList<>();
            ArrayList<Integer> result = new ArrayList<>();
            // Finish the implementation
            // You may need to add a new recursive method to do that
            boolean walkLeft = true;
            int currentIndex = 0;
            keyIndexStack.push(currentIndex);
            keyIndexQueue.add(currentIndex);
            while (!keyIndexStack.empty() || right[currentIndex] != -1) {
                if (walkLeft) {
                    if (left[currentIndex] != -1) {
                        currentIndex = left[currentIndex];
                        keyIndexQueue.add(currentIndex);
                        keyIndexStack.push(currentIndex);
                    } else {
                        keyIndexStack.pop();
                        walkLeft = false;
                        result.add(key[keyIndexQueue.remove()]);
                    }
                } else {
                    if (right[currentIndex] != -1) {
                        currentIndex = right[currentIndex];
                        keyIndexQueue.add(currentIndex);
                        keyIndexStack.push(currentIndex);
                        walkLeft = true;
                    } else {
                        if (!keyIndexStack.empty()) {
                            currentIndex = keyIndexStack.pop();
                            result.add(key[keyIndexQueue.remove()]);
                        }
                    }
                }
            }
            return result;
        }

        List<Integer> postOrder() {
            Stack<Integer> keyIndexStack = new Stack<>();
            HashSet<Integer> peekedSet = new HashSet<>();
            ArrayList<Integer> result = new ArrayList<>();
//            ArrayList<Integer> bothSidesHaveBeenChecked = new ArrayList<>();
            // Finish the implementation
            // You may need to add a new recursive method to do that
            boolean walkLeft = true;
            int currentIndex = 0;
            keyIndexStack.push(currentIndex);
//            while (!keyIndexStack.empty() || right[currentIndex] != -1) {
            while (!keyIndexStack.empty()) {
                if (peekedSet.contains(currentIndex)) {
                    result.add(key[currentIndex]);
                    peekedSet.remove(currentIndex);
                    keyIndexStack.pop();
                    if (keyIndexStack.empty()) break;
                    currentIndex = keyIndexStack.peek();
                    continue;
                }
                if (walkLeft) {
                    if (left[currentIndex] != -1) {
                        currentIndex = left[currentIndex];
                        keyIndexStack.push(currentIndex);
                    } else {
                        if (right[currentIndex] == -1) {
                            result.add(key[currentIndex]);
                            walkLeft = false;
                            keyIndexStack.pop();
                            currentIndex = keyIndexStack.peek();
                        } else {
                            peekedSet.add(currentIndex);
                            currentIndex = right[currentIndex];
                            keyIndexStack.push(currentIndex);
                        }
                    }
                } else {
                    if (right[currentIndex] != -1) {
                        peekedSet.add(currentIndex);
                        currentIndex = right[currentIndex];
                        keyIndexStack.push(currentIndex);
                        walkLeft = true;
                    } else {
                        result.add(key[currentIndex]);
                        int i = keyIndexStack.pop();
                        if (i != currentIndex)
                            result.add(key[i]);
                        if (keyIndexStack.empty()) break;
                        currentIndex = keyIndexStack.peek();
                    }
                }
            }
            return result;
        }
    }

    static public void main(String[] args) throws IOException {
        new Thread(null, new Runnable() {
            public void run() {
                try {
                    new TreeTraversal().run();
                } catch (IOException ignored) {
                }
            }
        }, "1", 1 << 26).start();
    }

    private void print(List<Integer> x) {
        for (Integer a : x) {
            System.out.print(a + " ");
        }
        System.out.println();
    }

    private void run() throws IOException {
        TreeOrders tree = new TreeOrders();
        tree.read();
        print(tree.inOrder());
        print(tree.preOrder());
        print(tree.postOrder());
    }
}