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;
}
static int getHeight(TreeNode root){
if(root == null){
return 0;
}
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}
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);
printEdge1(root);
printEdge2(root);
}
static void printEdge2(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val + " ");
if(root.left != null && root.right != null){
printLeftEdge(root.left,true);
printRightEdge(root.right,true);
}else {
printEdge2(root.left != null ? root.left : root.right);
}
System.out.println();
}
// 从上往下打印左边界，包括的处理了最后一层
static void printLeftEdge(TreeNode root, boolean print){
if(root == null){
return;
}
// 先打印根
if(print || (root.left == null && root.right == null)){
System.out.print(root.val + " ");
}
printLeftEdge(root.left, print);
// 只有当左节点为null的时候才打印右节点
printLeftEdge(root.right, print && root.left == null ? true : false);
}
// 从下往上打印右边界，包括的处理了最后一层
static void printRightEdge(TreeNode root, boolean print){
if(root == null){
return;
}
printRightEdge(root.left, print && root.right == null ? true : false);
printRightEdge(root.right, print);
if(print || (root.left == null && root.right == null)){
System.out.print(root.val + " ");
}
}
static void printEdge1(TreeNode root){
int height = getHeight(root);
TreeNode[] leftEdge = new TreeNode[height + 1];
TreeNode[] rightEdge = new TreeNode[height + 1];
// 叶子节点
List<TreeNode> leafList = new ArrayList<>();
// 左侧的
Queue<TreeNode> queue = new LinkedList<>();
Queue<Integer> queueC = new LinkedList<>();
queue.offer(root);
queueC.offer(1);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
int ceng = queueC.poll();
if(leftEdge[ceng] == null) {
leftEdge[ceng] = node;
}
if(node.left != null){
queue.offer(node.left);
queueC.offer(ceng + 1);
}
if(node.right != null){
queue.offer(node.right);
queueC.offer(ceng + 1);
}
}
// 右侧的
queue.offer(root);
queueC.offer(1);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
int ceng = queueC.poll();
if(rightEdge[ceng] == null) {
rightEdge[ceng] = node;
}
// 先右边再左边
if(node.right != null){
queue.offer(node.right);
queueC.offer(ceng + 1);
}
if(node.left != null){
queue.offer(node.left);
queueC.offer(ceng + 1);
}
}
// 非左，非右，且是叶子节点，按照每一层打印的
// queue.offer(root);
// queueC.offer(1);
// while (!queue.isEmpty()){
// TreeNode node = queue.poll();
// int ceng = queueC.poll();
// if(node.left == null && node.right == null && node != leftEdge[ceng] && node != rightEdge[ceng]) {
// leafList.add(node);
// }
// if(node.left != null){
// queue.offer(node.left);
// queueC.offer(ceng + 1);
// }
// if(node.right != null){
// queue.offer(node.right);
// queueC.offer(ceng + 1);
// }
// }
leafList = getLeafList(root, height,1,leftEdge,rightEdge);
// 一次打印即可
// 左
StringBuilder sb = new StringBuilder();
for(int i=1;i<=height;i++){
sb.append(leftEdge[i].val + " ");
}
// 叶子
for(TreeNode node: leafList){
sb.append(node.val + " ");
}
// 右
for(int i=height;i>=1;i--){
// 一层可能只有一个节点，左边打印了，则右边不需要打印了
if(rightEdge[i] != leftEdge[i]) {
sb.append(rightEdge[i].val + " ");
}
}
String s = sb.toString();
s = s.substring(0, s.length() - 1);
System.out.println(s);
return;
}
// 递归深度
static List<TreeNode> getLeafList(TreeNode root, int height, int curCeng,
TreeNode[] leftEdge, TreeNode[] rightEdge){
List<TreeNode> treeNodes = new ArrayList<>();
if(root == null){
return treeNodes;
}
if(root.left == null && root.right == null && root != leftEdge[curCeng] && root != rightEdge[curCeng]) {
treeNodes.add(root);
}
treeNodes.addAll(getLeafList(root.left, height, curCeng + 1, leftEdge, rightEdge));
treeNodes.addAll(getLeafList(root.right, height, curCeng + 1, leftEdge, rightEdge));
return treeNodes;
}
}
/*
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
44 44
44 18 10
18 22 1
22 40 0
40 0 34
34 36 0
36 31 0
31 0 0
1 41 9
41 30 27
30 0 19
19 0 0
27 16 0
16 32 0
32 0 0
9 3 39
3 0 12
12 0 0
39 20 11
20 4 0
4 0 0
11 0 0
10 38 2
38 7 0
7 23 35
23 0 8
8 42 0
42 0 0
35 0 28
28 0 0
2 14 21
14 6 0
6 24 0
24 15 43
15 0 0
43 0 5
5 33 0
33 26 0
26 0 0
21 17 25
17 29 13
29 0 0
13 0 0
25 0 37
37 0 0
44 18 22 40 34 36 31 5 33 26 19 32 12 4 11 42 28 15 29 13 43 37 25 21 2 10
44 18 22 40 34 36 31 19 32 12 4 11 42 28 15 26 29 13 37 25 21 2 10
*/