#include <bits/stdc++.h>
using namespace std;
 
#define SIZE 10000
vector<int> graph[SIZE];
bool visited[SIZE] = {0};
 
// For tree visited array is not required
void dfsForTree(int curr, int parent) {
	printf("%d ", curr);
 
	for(int i = 0;i < graph[curr].size();i++) {
		int adj = graph[curr][i];
		if(adj != parent)
			dfsForTree(adj, curr);
	}
}
 
void dfs(int curr) {
	printf("%d ", curr);
	visited[curr] = true;
 
	for(int adj: graph[curr]) {
		if(!visited[adj]) {
			dfs(adj);
		}
	}
}
 
int main() {
	int root;
 
	// Graph construction assumed as done
	dfsForTree(root, -1);
	dfs(root);
 
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIFNJWkUgMTAwMDAKdmVjdG9yPGludD4gZ3JhcGhbU0laRV07CmJvb2wgdmlzaXRlZFtTSVpFXSA9IHswfTsKCi8vIEZvciB0cmVlIHZpc2l0ZWQgYXJyYXkgaXMgbm90IHJlcXVpcmVkCnZvaWQgZGZzRm9yVHJlZShpbnQgY3VyciwgaW50IHBhcmVudCkgewoJcHJpbnRmKCIlZCAiLCBjdXJyKTsKCglmb3IoaW50IGkgPSAwO2kgPCBncmFwaFtjdXJyXS5zaXplKCk7aSsrKSB7CgkJaW50IGFkaiA9IGdyYXBoW2N1cnJdW2ldOwoJCWlmKGFkaiAhPSBwYXJlbnQpCgkJCWRmc0ZvclRyZWUoYWRqLCBjdXJyKTsKCX0KfQoKdm9pZCBkZnMoaW50IGN1cnIpIHsKCXByaW50ZigiJWQgIiwgY3Vycik7Cgl2aXNpdGVkW2N1cnJdID0gdHJ1ZTsKCglmb3IoaW50IGFkajogZ3JhcGhbY3Vycl0pIHsKCQlpZighdmlzaXRlZFthZGpdKSB7CgkJCWRmcyhhZGopOwoJCX0KCX0KfQoKaW50IG1haW4oKSB7CglpbnQgcm9vdDsKCgkvLyBHcmFwaCBjb25zdHJ1Y3Rpb24gYXNzdW1lZCBhcyBkb25lCglkZnNGb3JUcmVlKHJvb3QsIC0xKTsKCWRmcyhyb290KTsKCglyZXR1cm4gMDsKfQ==