#include<stdio.h>
#include<stdlib.h>
int b = 1;

typedef struct n {
	int a;
	struct n* l,* r;
}n,*N;

void XJL(N& l,int **a,int p,int q, int b) {//
	if (b == 0) {
		l = NULL;
		return;
	}
	else {
		l = (N)malloc(sizeof(n));
		l->a = b;
		l->l = NULL;
		l->r = NULL;
		XJL(l->l, a, p,2, a[b-1][0]);//
		XJL(l->r, a, p,2, a[b-1][1]);
	}
}

void ZBL(N l, int e) {//
	if (l == NULL) {
		return;
	}
	else {
		if(e == 1)
		printf("%d ", l->a);
		ZBL(l->l,e);
		if (e == 2)
		printf("%d ", l->a);
		ZBL(l->r,e);
		if (e == 3)
		printf("%d ", l->a);
	}
}

int main() {
	int n;
	N l;
	scanf("%d", &n);
	int** a = (int**)malloc(sizeof(int*) * n);
	for (int i = 0; i < n; i++)
	{
		a[i] = (int*)malloc(sizeof(int) * 2);
	}
    //之前这里我直接申请a[100000]来用
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			scanf("%d",&a[i][j]);
		}
	}
	XJL(l, a, n,2,b);
	ZBL(l,1); printf("\n");
	ZBL(l,2); printf("\n");
	ZBL(l,3); printf("\n");
	return 0;
}