#include<bits/stdc++.h>
using namespace std;
struct node{
	node *left,*right,*parent;
	int lr,value,depth,degree,script;
	bool isroot,isleaf;
};
node tr[1001];
int nodenum,qaq,qwq,root;
void pretra(node nod){
	cout<<nod.script<<":"<<nod.value<<' ';
	pretra(*nod.left);
	pretra(*nod.right);
}
void midtra(node nod){
	midtra(*nod.left);
	cout<<nod.script<<":"<<nod.value<<' ';
	midtra(*nod.right);
}
void postra(node nod){
	postra(*nod.left);
	postra(*nod.right);
	cout<<nod.script<<":"<<nod.value<<' ';
}
void getdepth(node &nod,int depth){
	nod.depth=depth;
	getdepth(*nod.left,depth+1);
	getdepth(*nod.right,depth+1);
}
void getlr(node &nod,int lr){
	nod.lr=lr;
	getdepth(*nod.left,lr-1);
	getdepth(*nod.right,lr+1);
}
int main(){
	//build
	cin>>nodenum;
	for(int i=0;i<nodenum;i++){
		cin>>tr[i].value>>qaq>>qwq;
		tr[i].script=i;
		if(qaq==-1&&qwq==-1){
			tr[i].isleaf=1;
			tr[i].degree=0;
			tr[i].left=NULL;
			tr[i].right=NULL;
		}else if(qaq==-1){
			tr[i].degree=1;
			tr[i].left=NULL;
			tr[i].right=&tr[qwq];
			tr[qwq].parent=&tr[i];
		}else if(qwq==-1){
			tr[i].degree=1;
			tr[i].right=NULL;
			tr[i].left=&tr[qaq];
			tr[qaq].parent=&tr[i];
		}else{
			tr[i].degree=2;
			tr[i].left=&tr[qaq];
			tr[i].right=&tr[qwq];
			tr[qaq].parent=&tr[i];
			tr[qwq].parent=&tr[i];
		}
	}
	//findroot
	for(int i=0;i<nodenum;i++){
		if(tr[i].parent==NULL){
			tr[i].isroot=1;
			root=i;
		}
		else tr[i].isroot=0;
	}
	//getdepth&lr
	getdepth(tr[root],1);
	getlr(tr[root],0);
	//traverasl
	pretra(tr[root]);
	cout<<"\n\n";
	midtra(tr[root]);
	cout<<"\n\n";
	postra(tr[root]);
}