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