centroid

#include <bits/stdc++.h>
#include <stdio.h>

#define pb push_back
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next nneexxtt
#define left lleefftt
#define right rriigghht

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;

const int N = (int)1e5 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;

int n, m, sub[100011];
vector<int> g[100011];
bool del[100011];

void dfs(int x, int par = -1) {
	sub[x] = 1;
	for(auto to : g[x]) {
		if(to == par || del[to]) continue;
		dfs(to, x);
		sub[x] += sub[to];
	}
}

int get_centroid(int x) {
	bool ch;
	int now = x, Sz = sub[x], par = -1;
	while(1) {
		ch = 0;
		for(auto to : g[now]) {
			if(to == par || del[to]) continue;
			if(sub[to] * 2 >= Sz) {
				par = now, now = to, ch = 1;
				break;
         }
		}
		if(!ch) break;
	}
	return now;
}

void show(int x, int par = -1) {
	cout << x << " ";
	for(auto to : g[x]) {
		if(to == par || del[to]) continue;
		show(to, x);
	}
}

void calc(int x, int par = -1) {
	dfs(x);
	x = get_centroid(x);
	cout << "\n\nCentroid: " << x << " Tree:\n";
	show(x);
	del[x] = 1;
	for(auto to : g[x]) {
		if(del[to] || to == par) continue;
		calc(to, x);
	}
}

int main() {
	cin >> n;
	for(int i = 1, a, b; i <= n - 1; i ++) {
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	calc(1);
	return 0;
}