import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayList;
public class Main {
public static ArrayList<ArrayList<Integer>> array;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int nCount = Integer.parseInt(br.readLine());
array = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < nCount; i++){
array.add(new ArrayList<Integer>());
}
for (int i = 0; i < nCount; i++){
StringTokenizer stk = new StringTokenizer(br.readLine());
int node = (int)stk.nextToken().charAt(0)-(int)'A';
String left = stk.nextToken();
String right = stk.nextToken();
if (left.equals(".")){
array.get(node).add(-1);
}
else{
int leftint = (int)left.charAt(0)-(int)'A';
array.get(node).add(leftint);
}
if (right.equals(".")){
array.get(node).add(-1);
}
else{
int rightint = (int)right.charAt(0)-(int)'A';
array.get(node).add(rightint);
}
}
printGraphToAdjList();
preorder(0);
System.out.println();
inorder(0);
System.out.println();
postorder(0);
System.out.println();
}
public static void printGraphToAdjList() {
for (int i = 0; i < array.size(); i++) {
System.out.print("정점 " + i + "의 인접리스트");
for (int j = 0; j < array.get(i).size(); j++) {
System.out.print(" -> " + array.get(i).get(j));
}
System.out.println();
}
}
public static void preorder(int x){
if (x == -1){
return;
}
System.out.print((char)(x+(int)'A'));
preorder(array.get(x).get(0));
preorder(array.get(x).get(1));
}
public static void inorder(int x){
if (x == -1){
return;
}
inorder(array.get(x).get(0));
System.out.print((char)(x+(int)'A'));
inorder(array.get(x).get(1));
}
public static void postorder(int x){
if (x == -1){
return;
}
postorder(array.get(x).get(0));
postorder(array.get(x).get(1));
System.out.print((char)(x+(int)'A'));
}
}