ac

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

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    static Map<Integer, Integer> leftArr = new HashMap<>();
    static Map<Integer, Integer> rightArr = new HashMap<>();

    // 递归建立树
    static TreeNode buildTree(TreeNode root, int val){
        if(root == null){
            root = new TreeNode(val);
        }
        int left = leftArr.get(val);
        int right = rightArr.get(val);
        if(left != 0){
            root.left = buildTree(root.left, left);
        }
        if(right != 0){
            root.right = buildTree(root.right, right);
        }
        return root;
    }

    public static void main(String[] args) throws Exception{
        String line;
        String[] strArr;
        line = reader.readLine();
        strArr = line.split(" ");
        int n = Integer.valueOf(strArr[0]);
        int rootVal = Integer.valueOf(strArr[1]);
        for (int i = 0; i < n; i++) {
            line = reader.readLine();
            strArr = line.split(" ");
            int curVal = Integer.valueOf(strArr[0]);
            int leftVal = Integer.valueOf(strArr[1]);
            int rightVal = Integer.valueOf(strArr[2]);
            leftArr.put(curVal,leftVal);
            rightArr.put(curVal, rightVal);
        }
        TreeNode root = null;
        root = buildTree(root, rootVal);
        preOrder(root);
        inOrder(root);
        morrisPost(root);
    }

    // 根 左 右
    static void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        boolean flag = true;
        StringBuilder sb = new StringBuilder();
        TreeNode cur = root;
        while (cur != null){
            if(cur.left == null){
                // 打印
                if(flag) {
                    sb.append(cur.val);
                    flag = false;
                }else {
                    sb.append(" " + cur.val);
                }
                cur = cur.right;
            }else {
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur){
                    pre = pre.right;
                }
                if(pre.right == null){ // 第一次访问
                    // 打印，建立联系，并转向左节点
                    if(flag) {
                        sb.append(cur.val);
                        flag = false;
                    }else {
                        sb.append(" " + cur.val);
                    }
                    pre.right = cur;
                    cur = cur.left;
                }else { // 第二次访问,表示cur的左子树都访问过了
                    pre.right = null;
                    cur = cur.right;
                }
            }
        }
        System.out.println(sb.toString());
        return;
    }

    // 左 根 右
    static void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        boolean flag = true;
        StringBuilder sb = new StringBuilder();
        TreeNode cur = root;
        while (cur != null){
            if(cur.left == null){
                // 打印
                if(flag) {
                    sb.append(cur.val);
                    flag = false;
                }else {
                    sb.append(" " + cur.val);
                }
                cur = cur.right;
            }else {
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur){
                    pre = pre.right;
                }
                if(pre.right == null){ // 第一次访问
                    // 建立联系，并转向左节点
                    pre.right = cur;
                    cur = cur.left;
                }else { // 第二次访问,表示cur的左子树都访问过了
                    // 打印
                    if(flag) {
                        sb.append(cur.val);
                        flag = false;
                    }else {
                        sb.append(" " + cur.val);
                    }
                    pre.right = null;
                    cur = cur.right;
                }
            }
        }
        System.out.println(sb.toString());
        return;
    }

    // 左 右 根
    static void morrisPost(TreeNode root){
        if(root == null){
            return;
        }
        TreeNode cur = root;
        while (cur != null){
            if(cur.left != null){
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur){
                    pre = pre.right;
                }
                if(pre.right == null){ // 第一次访问，只是先建立关联
                    pre.right = cur;
                    cur = cur.left;
                    continue;
                }else { // 第二次访问 cur
                    pre.right = null; // 切断联系
                    printEdge(cur.left);
                }
            }
            // 左边没有，先处理右边，才能处理根
            cur = cur.right;
        }
        // 根的右边界，逆序打印处理
        printEdge (root);
        System.out.println();
    }

    static boolean flag = true;

    static void printEdge(TreeNode head){
        // 逆序 head 的右边界
        TreeNode tail = reverseEdge(head);
        TreeNode cur = tail;
        while (cur != null){
            if(flag) {
                System.out.print(cur.val);
                flag = false;
            }else {
                System.out.print(" " + cur.val);
            }
            cur = cur.right;
        }
        // 逆序回去
        reverseEdge(tail);
    }

    // 逆序，通过 right 作为指针
    static TreeNode reverseEdge(TreeNode from){
        TreeNode preHead = null;
        while (from != null){
            TreeNode rightNext = from.right;

            from.right = preHead;
            preHead = from;

            from = rightNext;
        }
        return preHead;
    }

}
/*
         1
     /        \
  2              3
  \             /   \
  4            5     6
 / \          / \
7   8         9  10
     \       /
      11    12
     / \    / \
    13 14  15  16

16 1
1 2 3
2 0 4
4 7 8
7 0 0
8 0 11
11 13 14
13 0 0
14 0 0
3 5 6
5 9 10
10 0 0
9 12 0
12 15 16
15 0 0
16 0 0
6 0 0

1 2 4 7 11 13 14 15 16 12 10 6 3
1 2 4 7 13 14 15 16 10 6 3
*/