#include <iostream>
using namespace std;

int k;

struct Tree {
	int left,right;
}myTree[17];

void qianxu(int q) {
	//root -> leftson -> rightson
	if(q) {
		cout<<q<<" ";
		qianxu(myTree[q].left);
		qianxu(myTree[q].right); 
	} 
}

void zhongxu(int z) {
	//leftson -> root -> rightson
	if(z) {
		zhongxu(myTree[z].left);
		cout<<z<<" ";
		zhongxu(myTree[z].right);
	}
}

void houxu(int h) {
	//leftson -> rightson -> root
	if(h) {
		houxu(myTree[h].left);
		houxu(myTree[h].right);
		cout<<h<<" ";
	}
}

int main() {
	cin>>k;
	for(int i=1;i<=k;i++) {
		cin>>myTree[i].left>>myTree[i].right;
	}
	
	qianxu(1);
	cout<<endl;
	zhongxu(1);
	cout<<endl; 
	houxu(1);
	
	return 0;
}