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);

    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]);
        Map<Integer, TreeNode> mp = new HashMap<>(n);
        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]);
            if(!mp.containsKey(curVal)){
                mp.put(curVal, new TreeNode(curVal));
            }
            if(leftVal != 0){
                if(!mp.containsKey(leftVal)){
                    mp.put(leftVal, new TreeNode(leftVal));
                }
                mp.get(curVal).left = mp.get(leftVal);
            }
            if(rightVal != 0){
                if(!mp.containsKey(rightVal)){
                    mp.put(rightVal, new TreeNode(rightVal));
                }
                mp.get(curVal).right = mp.get(rightVal);
            }
        }
        TreeNode root = mp.get(rootVal);
        System.out.println(preOrder(root));
        System.out.println(bfs(root));
    }

    static String preOrder(TreeNode root){
        if(root == null){
            return "#!";
        }
        String res = root.val + "!";
        res += preOrder(root.left);
        res += preOrder(root.right);
        return res;
    }

    static TreeNode preOrder2Node(String s){
        if(s.equals("#!")){
            return null;
        }
        String[] stringArr = s.split("!");
        Queue<String> queue = new LinkedList<>();
        for(int i=0;i<stringArr.length;i++){
            queue.offer(stringArr[i]);
        }
        return preOrder2NodeQueue(queue);
    }

    static TreeNode preOrder2NodeQueue(Queue<String> queue){
        String value = queue.poll();
        if(value.equals("#")){
            return null;
        }
        TreeNode head = new TreeNode(Integer.valueOf(value));
        head.left = preOrder2NodeQueue(queue);
        head.right = preOrder2NodeQueue(queue);
        return head;
    }

    static String bfs(TreeNode root){
        if(root == null){
            return "#!";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node == null){
                sb.append("#!");
            }else {
                sb.append(node.val + "!");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return sb.toString();
    }

    static TreeNode bfs2Node(String s){
        if(s.equals("#")){
            return null;
        }

        String[] stringArr = s.split("!");
        TreeNode[] treeNodes = new TreeNode[stringArr.length];
        for(int i=0;i<stringArr.length;i++){
            if(stringArr[i].equals("#")){
                treeNodes[i] = null;
            }else {
                treeNodes[i] = new TreeNode(Integer.valueOf(stringArr[i]));
            }
        }

        int q = 0;
        int qLeft = 0;
        while (qLeft < treeNodes.length){
            if(treeNodes[q] == null){
                q ++;
            }else {
                if(qLeft < treeNodes.length){
                    treeNodes[q].left = treeNodes[qLeft];
                }
                if(qLeft + 1 < treeNodes.length){
                    treeNodes[q].right = treeNodes[qLeft + 1];
                }
                q ++; // q一步步移动
                qLeft += 2;
            }
        }
        return treeNodes[0];
    }

}
/*
         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
*/