import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int a = Integer.parseInt(s1[1]);
Tree root = new Tree(a);
Deque<Tree> queue = new LinkedList<>();
queue.addLast(root);
dfs(root,br,n,1);
qdfs(root);
System.out.println();
zdfs(root);
System.out.println();
hdfs(root);
}
public static void qdfs(Tree root){
if(root == null){
return;
}
System.out.print(root.val + " ");
if(root.left != null){
qdfs(root.left);
}
if(root.right != null){
qdfs(root.right);
}
}
public static void zdfs(Tree root){
if(root.left != null){
zdfs(root.left);
}
System.out.print(root.val + " ");
if(root.right != null){
zdfs(root.right);
}
}
public static void hdfs(Tree root){
if(root.left != null){
hdfs(root.left);
}
if(root.right != null){
hdfs(root.right);
}
System.out.print(root.val + " ");
}
public static void dfs(Tree root,BufferedReader br,int n,int index)throws IOException{
if(index > n){
return;
}
String[] str = br.readLine().split(" ");
if(!str[1].equals("0")){
Tree left = new Tree(Integer.parseInt(str[1]));
root.left = left;
dfs(left,br,n,index + 1);
}
if(!str[2].equals("0")){
Tree right = new Tree(Integer.parseInt(str[2]));
root.right = right;
dfs(right,br,n,index + 1);
}
}
}
class Tree{
int val;
Tree left;
Tree right;
public Tree(int val){
this.val = val;
}
}
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int a = Integer.parseInt(s1[1]);
Tree root = new Tree(a);
Deque<Tree> queue = new LinkedList<>();
queue.addLast(root);
dfs(root,br,n,1);
qdfs(root);
System.out.println();
zdfs(root);
System.out.println();
hdfs(root);
}
public static void qdfs(Tree root){
if(root == null){
return;
}
System.out.print(root.val + " ");
if(root.left != null){
qdfs(root.left);
}
if(root.right != null){
qdfs(root.right);
}
}
public static void zdfs(Tree root){
if(root.left != null){
zdfs(root.left);
}
System.out.print(root.val + " ");
if(root.right != null){
zdfs(root.right);
}
}
public static void hdfs(Tree root){
if(root.left != null){
hdfs(root.left);
}
if(root.right != null){
hdfs(root.right);
}
System.out.print(root.val + " ");
}
public static void dfs(Tree root,BufferedReader br,int n,int index)throws IOException{
if(index > n){
return;
}
String[] str = br.readLine().split(" ");
if(!str[1].equals("0")){
Tree left = new Tree(Integer.parseInt(str[1]));
root.left = left;
dfs(left,br,n,index + 1);
}
if(!str[2].equals("0")){
Tree right = new Tree(Integer.parseInt(str[2]));
root.right = right;
dfs(right,br,n,index + 1);
}
}
}
class Tree{
int val;
Tree left;
Tree right;
public Tree(int val){
this.val = val;
}
}