//Data Structure
//Binary Tree Traversal Pre-order, In-order, Post-order
#include <iostream>
#include <stdio.h>
#define MAX_M 26
using namespace std;
//adjacent list
char tree[MAX_M][2];
int tree_len[MAX_M];
void preorder_traverse(int node){
cout <<" "<< (char)(node + 'A');
if(tree_len[node] > 0) preorder_traverse(tree[node][0]);
if(tree_len[node] > 1) preorder_traverse(tree[node][1]);
}
void inorder_traverse(int node){
if(tree_len[node] > 0) inorder_traverse(tree[node][0]);
cout <<" "<< (char)(node + 'A');
if(tree_len[node] > 1) inorder_traverse(tree[node][1]);
}
void postorder_traverse(int node){
if(tree_len[node] > 0) postorder_traverse(tree[node][0]);
if(tree_len[node] > 1) postorder_traverse(tree[node][1]);
cout <<" "<< (char)(node + 'A');
}
int main(){
int T, test_case;
int N;
freopen ( "sample_input.txt", "r", stdin );
cin >> T;
for(test_case = 1; test_case <= T; test_case++){
//initialization
for(int i=0;i<MAX_M;i++){
tree_len[i]=0;
}
//input
cin >> N;
for(int i=0;i<N;i++){
char cp,cc;
cin >> cp >> cc;
tree[cp-'A'][tree_len[cp-'A']] = cc - 'A';
tree_len[cp - 'A']++;
if(tree_len[cp - 'A']>2){
cout << "OOPS!!" << endl;
}
}
cout << "adjacent tree" << endl;
for(int i=0;i<MAX_M;i++){
if(tree_len[i]!=0){
cout << (char)(i+'A') << ":";
for(int j=0;j<tree_len[i];j++){
cout << " " << (char)(tree[i][j] + 'A');
}
cout << endl;
}
}
//pre-order traversal(binary tree only)
cout << "preorder_traverse : " << endl;
preorder_traverse(0);
cout << endl;
//in-order traversal(binary tree only)
cout << "inorder_traverse : " << endl;
inorder_traverse(0);
cout << endl;
//post-order traversal(binar tree only)
cout << "postorder_traverse : " << endl;
postorder_traverse(0);
cout << endl;
//DFS
//BSF
}
return 0;
}