Asya loves animals very much. Recently, she purchased $n$ kittens, enumerated them from $1$ and $n$ and then put them into the cage. The cage consists of one row of $n$ cells, enumerated with integers from $1$ to $n$ from left to right. Adjacent cells had a partially transparent partition wall between them, hence there were $n - 1$ partitions originally. Initially, each cell contained exactly one kitten with some number.

Observing the kittens, Asya noticed, that they are very friendly and often a pair of kittens in neighboring cells wants to play together. So Asya started to remove partitions between neighboring cells. In particular, on the day $i$, Asya:  Noticed, that the kittens $x_i$ and $y_i$, located in neighboring cells want to play together.  Removed the partition between these two cells, efficiently creating a single cell, having all kittens from two original cells. 

Since Asya has never putted partitions back, after $n - 1$ days the cage contained a single cell, having all kittens.

For every day, Asya remembers numbers of kittens $x_i$ and $y_i$, who wanted to play together, however she doesn't remember how she placed kittens in the cage in the beginning. Please help her and find any possible initial arrangement of the kittens into $n$ cells.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 150\,000$) — the number of kittens.

Each of the following $n - 1$ lines contains integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$) — indices of kittens, which got together due to the border removal on the corresponding day.

It's guaranteed, that the kittens $x_i$ and $y_i$ were in the different cells before this day.


-----Output-----

For every cell from $1$ to $n$ print a single integer — the index of the kitten from $1$ to $n$, who was originally in it.

All printed integers must be distinct.

It's guaranteed, that there is at least one answer possible. In case there are multiple possible answers, print any of them.


-----Example-----
Input
5
1 4
2 5
3 1
4 5

Output
3 1 4 2 5



-----Note-----

The answer for the example contains one of several possible initial arrangements of the kittens.

The picture below shows how the cells were united for this initial arrangement. Note, that the kittens who wanted to play together on each day were indeed in adjacent cells. [Image]

Difficulty: MEDIUM_HARD
Tags: Spanning trees

Constructive algorithms

Starter code:

Solutions:
n = int(input())
parent = [i for i in range(n + 1)]
group = [[i] for i in range(n + 1)]
for i in range(n - 1):
	(x, y) = map(int, input().split())
	if len(group[parent[x]]) < len(group[parent[y]]):
		(x, y) = (y, x)
	group[parent[x]] += group[parent[y]]
	for j in group[parent[y]]:
		parent[j] = parent[x]
print(*group[parent[1]])


class UnionFind(object):
	__slots__ = ['nodes']

	def __init__(self, n: int) -> None:
		self.nodes = [-1] * n

	def get_root(self, x: int) -> int:
		if self.nodes[x] < 0:
			return x
		else:
			self.nodes[x] = self.get_root(self.nodes[x])
			return self.nodes[x]

	def unite(self, x: int, y: int) -> None:
		(root_x, root_y) = (self.get_root(x), self.get_root(y))
		if root_x != root_y:
			(bigroot, smallroot) = (root_x, root_y) if self.nodes[root_x] < self.nodes[root_y] else (root_y, root_x)
			self.nodes[bigroot] += self.nodes[smallroot]
			self.nodes[smallroot] = bigroot

def __starting_point():
	import sys
	n = int(input())
	queries = [tuple(map(int, l.split())) for l in sys.stdin]
	uf = UnionFind(n + 1)
	(get_root, unite) = (uf.get_root, uf.unite)
	groups = {}
	for (x, y) in queries:
		(x_root, y_root) = (get_root(x), get_root(y))
		if x_root not in groups:
			groups[x_root] = [x]
		if y_root not in groups:
			groups[y_root] = [y]
		unite(x, y)
		if x_root == get_root(x):
			groups[x_root].extend(groups[y_root])
		else:
			groups[y_root].extend(groups[x_root])
	print(*groups[get_root(1)])
__starting_point()


N = int(input())
P = [i for i in range(N)]
G = [[i] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	x = P[x]
	y = P[y]
	if len(G[x]) < len(G[y]):
		(x, y) = (y, x)
	G[x] += G[y]
	for k in G[y]:
		P[k] = x
print(' '.join(map(lambda x: str(x + 1), G[P[0]])))


n = int(input())
d = {}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	if a not in d.keys() and b not in d.keys():
		d[a] = [a, b]
		d[b] = d[a]
	elif a in d.keys() and b not in d.keys():
		d[a] += [b]
		d[b] = d[a]
	elif a not in d.keys() and b in d.keys():
		d[b] += [a]
		d[a] = d[b]
	else:
		d[a] += d[b]
		for j in d[b]:
			d[j] = d[a]
print(*d[1])


n = int(input())
head = list(range(n + 1))
group = [[i] for i in range(n + 1)]
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	(x, y) = (head[x], head[y])
	if len(group[x]) < len(group[y]):
		(x, y) = (y, x)
	group[x] += group[y]
	for z in group[y]:
		head[z] = x
print(*group[head[1]])


from sys import stdin
from collections import defaultdict, deque

class disjointset:

	def __init__(self, n):
		(self.rank, self.parent, self.n, self.nsets, self.edges) = (defaultdict(int), defaultdict(int), n, defaultdict(int), defaultdict(deque))
		for i in range(1, n + 1):
			(self.parent[i], self.nsets[i]) = (i, 1)
			self.edges[i] = deque([i])

	def find(self, x):
		if self.parent[x] == x:
			return x
		result = self.find(self.parent[x])
		self.parent[x] = result
		return result

	def union(self, x, y):
		(xpar, ypar) = (self.find(x), self.find(y))
		if xpar == ypar:
			return
		(par, child) = (0, 0)
		if self.rank[xpar] < self.rank[ypar]:
			(par, child) = (ypar, xpar)
		elif self.rank[xpar] > self.rank[ypar]:
			(par, child) = (xpar, ypar)
		else:
			(par, child) = (xpar, ypar)
			self.rank[xpar] += 1
		self.parent[child] = par
		self.edges[par].extendleft(self.edges[child])
n = int(input())
dis = disjointset(n)
for i in range(n - 1):
	(x, y) = map(int, input().split())
	dis.union(x, y)
print(*dis.edges[dis.find(1)])


N = int(input())
follow = [-1] * (N + 1)
num_follower = [1] * (N + 1)

def root_index_of(A):
	r = A
	while follow[r] > -1:
		r = follow[r]
	return r

def connected(A, B):
	return root_index_of(A) == root_index_of(B)

def connect(A, B):
	rA = root_index_of(A)
	rB = root_index_of(B)
	if rA == rB:
		return
	if num_follower[rA] < num_follower[rB]:
		follow[rA] = rB
		follow[A] = rB
		num_follower[rB] += num_follower[rA]
	else:
		follow[rB] = rA
		follow[B] = rA
		num_follower[rA] += num_follower[rB]
q = [tuple(map(int, input().split())) for _ in range(N - 1)]
g = dict()
for (x, y) in q:
	(x_root, y_root) = (root_index_of(x), root_index_of(y))
	if x_root not in g:
		g[x_root] = [x]
	if y_root not in g:
		g[y_root] = [y]
	connect(x, y)
	if x_root == root_index_of(x):
		g[x_root] += g[y_root]
	else:
		g[y_root] += g[x_root]
print(*g[root_index_of(1)])


class UnionFind(object):

	def __init__(self, n):
		self.root = [i for i in range(n)]
		self.size = [1 for _ in range(n)]
		self.data = [[i] for i in range(n)]

	def find(self, x):
		if self.root[x] == x:
			return x
		self.root[x] = self.find(self.root[x])
		return self.root[x]

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			return False
		if self.size[x] < self.size[y]:
			(x, y) = (y, x)
		self.root[y] = x
		self.size[x] += self.size[y]
		self.data[x].extend(self.data[y])

def main():
	n = int(input())
	uf = UnionFind(n + 1)
	for _ in range(n - 1):
		(x, y) = list(map(int, input().split()))
		uf.union(x, y)
	x = uf.find(1)
	print(*uf.data[x])

def __starting_point():
	main()
__starting_point()


t = int(input())
p = [c for c in range(1, t + 1)]
lst = [c for c in range(1, t + 1)]
b = [[c] for c in range(1, t + 1)]
for c in range(t - 1):
	(m, n) = map(int, input().split())
	while p[n - 1] != lst[n - 1]:
		n = p[n - 1]
	while p[m - 1] != lst[m - 1]:
		m = p[m - 1]
	if m < n:
		t = m
		m = n
		n = t
	p[m - 1] = n
	b[n - 1] += b[m - 1]
print(*b[0])


class UnionFind:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.rank = [0 for _ in range(n + 1)]
		self.size = [1] * (n + 1)
		self.group = [[i] for i in range(n + 1)]

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			self.parent[x] = self.find(self.parent[x])
			return self.parent[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.parent[x] = y
			self.size[y] += self.size[x]
		else:
			self.parent[y] = x
			self.size[x] += self.size[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def merge(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if len(self.group[x]) < len(self.group[y]):
			(x, y) = (y, x)
		self.group[x].extend(self.group[y])
		self.group[y] = []
		self.parent[y] = x

	def check_same(self, x, y):
		return self.find(x) == self.find(y)

	def get_size(self, x):
		return self.size[self.find(x)]
N = int(input())
items = []
for i in range(N - 1):
	items.append(tuple(map(int, input().split())))
union_find = UnionFind(N)
for (a, b) in items:
	union_find.merge(a, b)
ans = union_find.group[union_find.find(1)]
print(*ans)


def find(x):
	if par[x] == x:
		return x
	par[x] = find(par[x])
	return par[x]

def union(x, y):
	px = find(x)
	py = find(y)
	if px != py:
		if count[px] > count[py]:
			(px, py) = (py, px)
		count[py] += count[px]
		arr[par[px]] = child[py]
		child[py] = child[px]
		par[px] = py
n = int(input())
par = [i for i in range(n + 1)]
child = [i for i in range(n + 1)]
arr = [-1 for i in range(n + 1)]
count = [0 for i in range(n + 1)]
for i in range(n - 1):
	(l, r) = map(int, input().split())
	union(l, r)
pt = 0
inv_arr = [-1 for i in range(n + 1)]
for i in range(1, n + 1):
	if arr[i] == -1:
		pt = i
		continue
	if arr[i] > 0:
		inv_arr[arr[i]] = i
ans = [pt]
while inv_arr[pt] > 0:
	ans.append(inv_arr[pt])
	pt = inv_arr[pt]
print(*ans)


n = int(input())
m = [[] for i in range(n + 1)]
p = [0] * (n + 1)

def make_set(u):
	global p
	global m
	p[u] = u
	m[u].append(u)

def get_set(u):
	global p
	if p[u] == u:
		return u
	p[u] = get_set(p[u])
	return p[u]

def union_sets(u, v):
	global p
	global m
	u = get_set(u)
	v = get_set(v)
	if u == v:
		return
	if len(m[u]) > len(m[v]):
		(u, v) = (v, u)
	for elem in m[u]:
		m[v].append(elem)
	p[u] = v
for i in range(0, n, 1):
	make_set(i)
for i in range(0, n - 1, 1):
	(x, y) = map(int, input().split())
	union_sets(x - 1, y - 1)
j = get_set(0)
for i in range(0, n, 1):
	ans = m[j][i] + 1
	print(ans, end=' ')


from sys import *
n = int(stdin.readline())
(parent, L, R, left, right) = ({}, {}, {}, {}, {})
for i in range(1, n + 1):
	parent[i] = i
	L[i] = R[i] = i
	left[i] = right[i] = None

def find(i):
	root = i
	while parent[root] != root:
		root = parent[root]
	while i != root:
		j = parent[i]
		parent[i] = root
		i = j
	return root

def union(i, j):
	(i, j) = (find(i), find(j))
	parent[i] = j
	(a, b, c, d) = (L[i], R[i], L[j], R[j])
	(L[j], R[j]) = (a, d)
	(right[b], left[c]) = (c, b)
for i in range(n - 1):
	(u, v) = stdin.readline().split(' ')
	union(int(u), int(v))
ans = []
root = L[find(1)]
for i in range(n):
	ans.append(root)
	root = right[root]
print(' '.join([str(i) for i in ans]))


import sys
input = sys.stdin.readline
n = int(input())
container = [[i] for i in range(n + 1)]
parent = [i for i in range(n + 1)]

def par(x):
	while x != parent[x]:
		x = parent[x]
	return x
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	p1 = par(x)
	p2 = par(y)
	if p1 < p2:
		container[p1] += container[p2]
		parent[p2] = p1
	else:
		container[p2] += container[p1]
		parent[p1] = p2
print(*container[1])


n = int(input())
d = dict()

def ppp(d):
	for (k, v) in list(d.items()):
		print(k, ':', v.s, ':', id(v))
	print('-----')

class A:

	def __init__(self):
		self.s = []
for _ in range(n - 1):
	(a, b) = list(map(int, input().split()))
	if a not in d and b not in d:
		t = A()
		t.s.append(a)
		t.s.append(b)
		d[a] = t
		d[b] = t
	elif a in d and b not in d:
		d[a].s.append(b)
		d[b] = d[a]
	elif a not in d and b in d:
		d[b].s.append(a)
		d[a] = d[b]
	else:
		d[a].s.extend(d[b].s)
		for x in d[b].s:
			d[x] = d[a]
print(*d[1].s)


class DisjointSets:
	parent = {}
	rank = {}
	ls = {}

	def __init__(self, n):
		for i in range(1, n + 1):
			self.makeSet(i)

	def makeSet(self, node):
		self.node = node
		self.parent[node] = node
		self.rank[node] = 1
		self.ls[node] = [node]

	def find(self, node):
		parent = self.parent
		if parent[node] != node:
			parent[node] = self.find(parent[node])
		return parent[node]

	def union(self, node, other):
		node = self.find(node)
		other = self.find(other)
		if self.rank[node] > self.rank[other]:
			self.parent[other] = node
			self.ls[node].extend(self.ls[other])
		elif self.rank[other] > self.rank[node]:
			self.parent[node] = other
			self.ls[other].extend(self.ls[node])
		else:
			self.parent[other] = node
			self.ls[node] += self.ls[other]
			self.rank[node] += 1
n = int(input())
ds = DisjointSets(n)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	ds.union(a, b)
print(' '.join(map(str, ds.ls[ds.find(1)])))


n = int(input())
p = list(range(n + 1))
c = [[i] for i in range(n + 1)]
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	(x, y) = (p[x], p[y])
	if len(c[x]) < len(c[y]):
		(x, y) = (y, x)
	c[x] += c[y]
	for z in c[y]:
		p[z] = x
print(*c[p[1]])


import sys

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = sys.stdin.readline().split()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_int(self):
		return int(self.next())

	def solve(self):
		n = self.next_int()
		fa = [-1 for _ in range(0, n)]
		nx = [i for i in range(0, n)]
		la = [i for i in range(0, n)]
		for _ in range(1, n):
			a = self.find(self.next_int() - 1, fa)
			b = self.find(self.next_int() - 1, fa)
			fa[a] = b
			nx[la[b]] = a
			la[b] = la[a]
		ii = 0
		while fa[ii] != -1:
			ii += 1
		ans = []
		for _ in range(0, n):
			ans.append(str(ii + 1))
			ii = nx[ii]
		print(' '.join(ans))

	def find(self, k, fa):
		if fa[k] == -1:
			return k
		fa[k] = self.find(fa[k], fa)
		return fa[k]
Main().solve()


n = int(input())
ks = [[0]]
for i in range(n):
	ks.append([i + 1])
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	while type(ks[a]) == int:
		a = ks[a]
	while type(ks[b]) == int:
		b = ks[b]
	if len(ks[a]) >= len(ks[b]):
		ks[a] += ks[b]
		ks[b] = a
	else:
		ks[b] += ks[a]
		ks[a] = b
	if _ == n - 2:
		while type(ks[a]) == int:
			a = ks[a]
		print(*ks[a])


n = int(input())
a = [[0, 0] for i in range(n - 1)]
for i in range(n - 1):
	tp = [int(x) for x in input().split()]
	(a[i][0], a[i][1]) = (tp[0], tp[1])
d = dict()
for i in range(1, n + 1):
	d[i] = -1
s = [a[0]]
d[a[0][0]] = 0
d[a[0][1]] = 0
for i in range(1, n - 1):
	t0 = d[a[i][0]]
	t1 = d[a[i][1]]
	if t0 == -1 and t1 == -1:
		s.append(a[i])
		d[a[i][0]] = len(s) - 1
		d[a[i][1]] = len(s) - 1
	elif t0 != -1 and t1 != -1:
		if len(s[t0]) > len(s[t1]):
			s[t0] += s[t1]
			for ii in s[t1]:
				d[ii] = t0
		else:
			s[t1] += s[t0]
			for ii in s[t0]:
				d[ii] = t1
	elif t0 == -1 and t1 != -1:
		s[t1].append(a[i][0])
		d[a[i][0]] = t1
	elif t0 != -1 and t1 == -1:
		s[t0].append(a[i][1])
		d[a[i][1]] = t0
for i in range(len(s)):
	if len(s[i]) == n:
		print(*s[i], sep=' ')
		break


class Disjoint_set:

	class node:

		def __init__(self, a):
			self.value = a
			self.p = self
			self.rank = 0
			self.ans = [a]

	def __init__(self, a):
		self.data = {i: self.make_set(i) for i in range(1, a + 1)}

	def make_set(self, val):
		return self.node(val)

	def union(self, x, y):
		self.link(self.find_set(self.data[x]), self.find_set(self.data[y]))

	def link(self, val1, val2):
		if val1.rank > val2.rank:
			val2.p = val1
			val1.ans.extend(val2.ans)
			val1.rank += 1
		else:
			val1.p = val2
			val2.ans.extend(val1.ans)
			val2.rank += 1

	def find_set(self, val):
		if val.p.value != val.value:
			val.p = self.find_set(val.p)
		return val.p

	def sol(self):
		x = 1
		for i in self.data:
			x = i
			break
		print(*self.find_set(self.data[x]).ans)
n = int(input())
a = [list(map(int, input().split())) for i in range(n - 1)]
sa = Disjoint_set(n)
for (i, j) in a:
	sa.union(i, j)
sa.sol()


import sys
from collections import defaultdict, deque

def get_parent(num, parent):
	while parent[num] != num:
		num = parent[num]
	return num

def union(dic, roota, rootb, parent, child):
	(parenta, parentb) = (get_parent(roota, parent), get_parent(rootb, parent))
	(childa, childb) = (child[parenta], child[parentb])
	if childa > childb:
		parent[parentb] = parenta
		child[parenta] += childb
		for i in dic[parentb]:
			dic[parenta].append(i)
	else:
		parent[parenta] = parentb
		child[parentb] += childa
		for i in dic[parenta]:
			dic[parentb].append(i)
n = int(sys.stdin.readline())
graph = defaultdict(list)
nodes = [[0, 0] for _ in range(n - 1)]
for _ in range(n - 1):
	(u, v) = map(int, sys.stdin.readline().split())
	nodes[_] = [u, v]
parent = [i for i in range(n + 1)]
child = [1 for i in range(n + 1)]
dic = defaultdict(list)
for i in range(1, n + 1):
	dic[i].append(i)
for (x, y) in nodes:
	union(dic, x, y, parent, child)
y = get_parent(1, parent)
print(*dic[y])


import sys
import bisect
from random import randint
input = lambda : sys.stdin.readline().strip('\r\n')
from math import gcd
sa = lambda : input()
sb = lambda : int(input())
sc = lambda : input().split()
sd = lambda : list(map(int, input().split()))
se = lambda : float(input())
sf = lambda : list(input())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7

def hnbhai():
	n = int(input())
	a = [i for i in range(n + 1)]
	g = [[i] for i in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = sd()
		(x, y) = (a[x], a[y])
		if len(g[x]) < len(g[y]):
			(x, y) = (y, x)
		g[x] += g[y]
		for i in g[y]:
			a[i] = x
	print(*g[a[1]])
for _ in range(1):
	hnbhai()


def find(x):
	while parent[x] != x:
		x = parent[x]
	return x

def union(x, y):
	a = find(x)
	b = find(y)
	if a != b:
		parent[a] = parent[b] = min(a, b)
n = int(input())
p = [list(map(int, input().split())) for i in range(n - 1)]
parent = [i for i in range(n + 1)]
ans = [[i] for i in range(n + 1)]
for (x, y) in p:
	a = find(x)
	b = find(y)
	if b < a:
		ans[b] += ans[a]
	else:
		ans[a] += ans[b]
	union(x, y)
print(*ans[1])


n = int(input())

class Element:

	def __init__(self, x):
		self.things = [x]
		self.rep = x

class DisjSet:

	def __init__(self, n):
		self.rank = [1] * n
		self.elements = [Element(x) for x in range(n)]

	def find(self, x):
		if self.elements[x].rep != x:
			self.elements[x].rep = self.find(self.elements[x].rep)
		return self.elements[x].rep

	def Union(self, x, y):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			return
		if self.rank[xset] < self.rank[yset]:
			self.elements[xset].rep = yset
			self.elements[yset].things.extend(self.elements[xset].things)
		elif self.rank[xset] > self.rank[yset]:
			self.elements[yset].rep = xset
			self.elements[xset].things.extend(self.elements[yset].things)
		else:
			self.elements[yset].rep = xset
			self.rank[xset] = self.rank[xset] + 1
			self.elements[xset].things.extend(self.elements[yset].things)
obj = DisjSet(n)
for _ in range(n - 1):
	(a, b) = list(map(lambda x: int(x), input().split()))
	obj.Union(a - 1, b - 1)
for ele in obj.elements:
	if len(ele.things) == n:
		print(*[x + 1 for x in ele.things])


n = int(input())

class Leader(object):

	def __init__(self, value):
		self.array = [value]

def union(v1, v2):
	leader = v1 if len(dsets[v1].array) >= len(dsets[v2].array) else v2
	antileader = v1 if leader == v2 else v2
	dsets[leader].array.extend(dsets[antileader].array)
	for v in dsets[antileader].array:
		dsets[v] = dsets[leader]
dsets = [Leader(i) for i in range(n)]
for _ in range(n - 1):
	(v1, v2) = [int(t) - 1 for t in input().split(' ')]
	union(v1, v2)
print(' '.join((str(t + 1) for t in dsets[0].array)))


import sys
input = sys.stdin.readline

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.left = [-1] * n
		self.right = [-1] * n
		self.most_right = [i for i in range(n)]

	def root(self, x):
		p = x
		while not self.par[p] < 0:
			p = self.par[p]
		while x != p:
			tmp = x
			x = self.par[x]
			self.par[tmp] = p
		return p

	def unite(self, x, y):
		(rx, ry) = (self.root(x), self.root(y))
		self.par[ry] = rx
		self.left[ry] = self.most_right[rx]
		self.right[self.most_right[rx]] = ry
		self.most_right[rx] = self.most_right[ry]
n = int(input())
uf = Unionfind(n)
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	uf.unite(x - 1, y - 1)
ans = []
for i in range(n):
	if uf.left[i] == -1:
		ans.append(i)
		break
for _ in range(n - 1):
	ans.append(uf.right[ans[-1]])
ans = list(map(lambda x: x + 1, ans))
print(*ans)


import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(readline())
(*p,) = range(N)
xs = [0] * N
sz = [1] * N

def root(x):
	if x == p[x]:
		return x
	z = p[x]
	p[x] = y = root(p[x])
	xs[x] += xs[z]
	return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if px == py:
		return
	if px < py:
		p[py] = px
		xs[py] = sz[px]
		sz[px] += sz[py]
	else:
		p[px] = py
		xs[px] = sz[py]
		sz[py] += sz[px]
for i in range(N - 1):
	(x, y) = map(int, readline().split())
	unite(x - 1, y - 1)
cur = 0
ds = [0] * N
for i in range(N):
	root(i)
	if xs[i] == 0:
		ds[i] = cur
		cur += sz[i]
ans = [0] * N
for i in range(N):
	ans[xs[i] + ds[root(i)]] = i + 1
print(*ans)


import collections
import heapq
import bisect
import math
import time

class Solution2:

	def solve(self, A1, A2):
		pass

def gcd(a, b):
	if not b:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return b * a // gcd(b, a)

class Node:

	def __init__(self, val):
		self.val = val
		self.next = None
		self.prev = None

class Solution:

	def solve(self, days):

		def union(i, j):
			(l_i, l_j) = (find(i), find(j))
			sets[l_j] = sets[i] = sets[j] = l_i

		def find(i):
			while i != sets[i]:
				i = sets[i]
			return i
		sets = list(range(len(days) + 1))
		tails = [Node(i) for i in range(len(days) + 1)]
		nodes = [tails[i] for i in range(len(days) + 1)]
		for (a, b) in days:
			(l_b, l_a) = (find(b - 1), find(a - 1))
			nodes[l_b].next = tails[l_a]
			tails[l_a].prev = nodes[l_b]
			tails[l_a] = tails[l_b]
			union(a - 1, b - 1)
		for i in range(len(days) + 1):
			if sets[i] == i:
				out = []
				curr = nodes[i]
				while curr:
					out.append(curr.val)
					curr = curr.prev
				return [k + 1 for k in out]
sol = Solution()
sol2 = Solution2()
for test_case in range(1):
	N = input()
	a = []
	for _ in range(int(N) - 1):
		a.append([int(c) for c in input().split()])
	out = sol.solve(a)
	print(' '.join([str(o) for o in out]))


from sys import stdin, stdout
n = int(stdin.readline())

class DSUNode:
	p = int()
	right = int()
	next = int()

	def __init__(self, p):
		self.p = p
		self.back = p
		self.next = None
dsu = [DSUNode(i) for i in range(n + 1)]

def find(x):
	if dsu[x].p != x:
		dsu[x].p = find(dsu[x].p)
	return dsu[x].p
for w in range(n - 1):
	(x, y) = map(int, stdin.readline().split())
	(x, y) = (find(x), find(y))
	dsu[y].p = x
	dsu[dsu[x].back].next = y
	dsu[x].back = dsu[y].back
it = find(1)
while it != None:
	stdout.write(str(it) + ' ')
	it = dsu[it].next


from collections import defaultdict
import sys
import bisect
input = sys.stdin.readline

def find(x):
	while p[x] != x:
		x = p[p[x]]
	return x

def union(a, b):
	if sz[a] > sz[b]:
		p[b] = a
		ans[a] += ans[b]
	elif sz[a] < sz[b]:
		p[a] = b
		ans[b] += ans[a]
	else:
		p[b] = a
		ans[a] += ans[b]
		sz[a] += 1
n = int(input())
p = [i for i in range(n)]
ans = [[i] for i in range(n)]
sz = [0] * n
for ii in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	a = find(u)
	b = find(v)
	union(a, b)
(leng, out) = (0, [])
for i in ans:
	if len(i) > leng:
		leng = len(i)
		out = i
out = [i + 1 for i in out]
print(*out)


n = int(input())
import heapq
from collections import defaultdict
graph = defaultdict(set)
for x in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a].add((x, b))
	graph[b].add((x, a))
order = []
seen = set()
start = 1
q = list(graph[start])
heapq.heapify(q)
while q:
	(t, node) = heapq.heappop(q)
	if node in seen:
		continue
	seen.add(node)
	order.append(node)
	for neighbor in graph[node]:
		heapq.heappush(q, neighbor)
print(*order)


import sys
import math
MAXN = 150001
parent = [None] * MAXN
rank = [0] * MAXN
lists = [None] * MAXN

class Node:

	def __init__(self, value, next_node=None):
		self.value = value
		self.next_node = next_node

	def __str__(self):
		return 'Node: {}'.format(self.value)

class LinkedList:

	def __init__(self, head, tail=None):
		self.head = head
		self.tail = tail
		self.curr = None

	def __iter__(self):
		self.curr = self.head
		return self

	def __next__(self):
		if self.curr is not None:
			value = self.curr.value
			self.curr = self.curr.next_node
			return value
		else:
			raise StopIteration

	def extend(self, other):
		self.tail.next_node = other.head
		self.tail = other.tail

def make_set(x):
	parent[x] = x
	x_node = Node(x)
	lists[x] = LinkedList(x_node, x_node)

def find_set(x):
	if parent[x] == x:
		return x
	parent[x] = find_set(parent[x])
	return parent[x]

def union(x, y):
	x = find_set(x)
	y = find_set(y)
	if x == y:
		return
	if rank[x] < rank[y]:
		(x, y) = (y, x)
	parent[y] = x
	lists[x].extend(lists[y])
	if rank[x] == rank[y]:
		rank[x] += 1
n = int(input())
for x in range(1, n + 1):
	make_set(x)
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	union(x, y)
root = find_set(1)
result = lists[root]
print(' '.join(map(str, result)))


from sys import stdin, stdout
import collections
import math
N = int(input())
label = [0] * (N + 1)
path = [[x] for x in range(N + 1)]
for i in range(1, N + 1):
	label[i] = i

def getRoot(i):
	while i != label[i]:
		i = label[i]
	return i

def union(u, v):
	rootU = getRoot(u)
	rootV = getRoot(v)
	label[rootU] = min(rootU, rootV)
	label[rootV] = min(rootU, rootV)
	if rootU > rootV:
		path[rootV] += path[rootU]
	else:
		path[rootU] += path[rootV]
for i in range(N - 1):
	(u, v) = [int(x) for x in stdin.readline().split()]
	union(u, v)
print(*path[1])


n = int(input())
p = [[i, i, i] for i in range(n + 1)]

def asd(i):
	if i == p[i][0]:
		return i
	p[i][0] = asd(p[i][0])
	return p[i][0]

def qwe(i, j):
	i = asd(i)
	j = asd(j)
	p[i][0] = p[j][0]
	p[p[i][2]][2] = p[p[j][1]][1]
	p[j][1] = p[i][1]
	return i
s = 0
while n > 1:
	n -= 1
	(x, y) = map(int, input().split())
	s = qwe(x, y)

def asd(s):
	while True:
		yield s
		if p[s][2] == s:
			break
		s = p[s][2]
print(' '.join(map(str, asd(p[s][1]))))


import sys
input = sys.stdin.readline
n = int(input())
P = [list(map(int, input().split())) for i in range(n - 1)]
Group = [i for i in range(n + 1)]

def find(x):
	while Group[x] != x:
		x = Group[x]
	return x

def Union(x, y):
	if find(x) != find(y):
		Group[find(y)] = Group[find(x)] = min(find(y), find(x))
ANS = [[i] for i in range(n + 1)]
for (i, j) in P:
	if find(j) < find(i):
		ANS[find(j)] += ANS[find(i)]
	else:
		ANS[find(i)] += ANS[find(j)]
	Union(i, j)
for a in ANS[1]:
	print(a, end=' ')


def asya(l):
	sets = [[i] for i in range(len(l) + 1)]
	elems = list(range(len(l) + 1))
	for i in l:
		s1 = elems[i[0]]
		s2 = elems[i[1]]
		if len(sets[s1]) < len(sets[s2]):
			for i in sets[s1]:
				sets[s2] += [i]
				elems[i] = s2
			sets[s1] = []
		else:
			for i in sets[s2]:
				sets[s1] += [i]
				elems[i] = s1
			sets[s2] = []
	return sets[elems[0]]
n = int(input())
l = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	l += [[a - 1, b - 1]]
q = asya(l)
for i in range(len(q)):
	q[i] += 1
print(*q)


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
p = [i for i in range(200000)]
r = [1 for i in range(200000)]

def find(x):
	if p[x] != x:
		p[x] = find(p[x])
	return p[x]

def union(x, y):
	u = find(x)
	v = find(y)
	if u != v:
		if r[u] >= r[v]:
			p[v] = u
			r[u] += r[v]
			g[u] += g[v]
		else:
			p[u] = v
			r[v] += r[u]
			g[v] += g[u]
g = [[i] for i in range(200000)]
(n,) = I()
for i in range(n - 1):
	(x, y) = I()
	if find(x) != find(y):
		union(x, y)
for i in range(1, n + 1):
	if len(g[i]) == n:
		print(*g[i])
		exit()


class DisjointSets:
	parent = {}
	rank = {}
	ls = {}

	def __init__(self, n):
		for i in range(1, n + 1):
			self.makeSet(i)

	def makeSet(self, node):
		self.node = node
		self.parent[node] = node
		self.rank[node] = 1
		self.ls[node] = [node]

	def find(self, node):
		curnode = node
		parent = self.parent
		while parent[curnode] != curnode:
			curnode = parent[curnode]
		root = curnode
		curnode = node
		while parent[curnode] != root:
			parent[curnode] = root
		return root

	def union(self, node, other):
		node = self.find(node)
		other = self.find(other)
		if self.rank[node] > self.rank[other]:
			self.parent[other] = node
			self.ls[node].extend(self.ls[other])
		elif self.rank[other] > self.rank[node]:
			self.parent[node] = other
			self.ls[other].extend(self.ls[node])
		else:
			self.parent[other] = node
			self.ls[node] += self.ls[other]
			self.rank[node] += 1
n = int(input())
ds = DisjointSets(n)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	ds.union(a, b)
ans = ds.ls[ds.find(1)]
for a in ans:
	print(a, end=' ')


from array import array
KittenQuant = int(input())
CacheParts = []
KittenIndexes = array('i', [-1] * (KittenQuant + 1))
for i in range(KittenQuant - 1):
	(Left, Right) = map(int, input().split())
	IndexLeft = KittenIndexes[Left]
	IndexRight = KittenIndexes[Right]
	if IndexLeft == -1 and IndexRight == -1:
		NewIndex = len(CacheParts)
		CacheParts.append(array('i', [Left, Right]))
		KittenIndexes[Left] = NewIndex
		KittenIndexes[Right] = NewIndex
	elif IndexLeft != -1 and IndexRight == -1:
		CacheParts[IndexLeft].append(Right)
		KittenIndexes[Right] = IndexLeft
	elif IndexLeft == -1 and IndexRight != -1:
		CacheParts[IndexRight].append(Left)
		KittenIndexes[Left] = IndexRight
	elif len(CacheParts[IndexLeft]) >= len(CacheParts[IndexRight]):
		CacheParts[IndexLeft].extend(CacheParts[IndexRight])
		for item in CacheParts[IndexRight]:
			KittenIndexes[item] = IndexLeft
	else:
		CacheParts[IndexRight].extend(CacheParts[IndexLeft])
		for item in CacheParts[IndexLeft]:
			KittenIndexes[item] = IndexRight
print(*CacheParts[KittenIndexes[1]])


(n,) = map(int, input().split())
p = [i for i in range(0, n + 1)]

def find(i):
	if p[i] == i:
		return i
	par = find(p[i])
	p[i] = par
	return par

def join(a, b):
	p[find(a)] = find(b)
N = [-1 for i in range(0, n + 1)]

class List:

	def __init__(self, val):
		self.front = self
		self.value = val
		self.rear = self
		self.next = None

	def add(self, other):
		self.rear.next = other
		self.rear = other.rear
		other.front = self
m = {i: List(i) for i in range(1, n + 1)}

def printList(i):
	if i is None:
		return
	list = []
	while i != None:
		list.append(i.value)
		i = i.next
	print(str(list).replace(',', '').replace('[', '').replace(']', ''))
ans = 1
for i in range(1, n):
	(a, b) = map(int, input().split())
	m[find(a)].add(m[find(b)])
	temp = m[find(a)]
	del m[find(a)]
	del m[find(b)]
	join(a, b)
	key = find(a)
	ans = key
	m[key] = temp.front
printList(m[ans].front)


[n] = [int(x) for x in input().split()]
location = [-1] * (n + 10)
lists = []
for i in range(0, n - 1):
	[x, y] = [int(x) for x in input().split()]
	if location[x] == -1 and location[y] == -1:
		location[x] = len(lists)
		location[y] = len(lists)
		lists.append([x, y])
	elif location[x] == -1 or location[y] == -1:
		if location[x] == -1:
			t = y
			y = x
			x = t
		location[y] = location[x]
		lists[location[x]].append(y)
	else:
		list_x = lists[location[x]]
		list_y = lists[location[y]]
		if len(list_x) > len(list_y):
			t = list_y
			list_y = list_x
			list_x = t
			t = y
			y = x
			x = y
		for e in list_x:
			location[e] = location[y]
		list_y += list_x
print(' '.join([str(x) for x in lists[location[1]]]))


from sys import stdin
max_val = int(10000000000000.0)
min_val = int(-10000000000000.0)

def read_int():
	return int(stdin.readline())

def read_ints():
	return [int(x) for x in stdin.readline().split()]

def read_str():
	return input()

def read_strs():
	return [x for x in stdin.readline().split()]
import heapq
from collections import defaultdict
n = int(input())
graph = defaultdict(set)
for x in range(n - 1):
	(a, b) = [int(x) for x in input().split()]
	graph[a].add((x, b))
	graph[b].add((x, a))
order = []
seen = set()
begin = 1
q = list(graph[begin])
heapq.heapify(q)
while q:
	(t, node) = heapq.heappop(q)
	if node in seen:
		continue
	seen.add(node)
	order.append(node)
	for neighbor in graph[node]:
		heapq.heappush(q, neighbor)
print(*order)


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)

def find(x):
	if p[x] == x:
		return x
	p[x] = find(p[x])
	return p[x]

def merge(x, y):
	a = find(x)
	b = find(y)
	if a != b:
		if sz[a] > sz[b]:
			(a, b) = (b, a)
		p[a] = b
		sz[b] += sz[a]
		arr[b].extend(arr[a])
n = int(input())
p = [i for i in range(n + 1)]
sz = [1 for i in range(n + 1)]
arr = [[i] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	merge(u, v)
for i in arr:
	if len(i) == n:
		for j in i:
			print(j, end=' ')
		print()
		break


import sys
from collections import deque
import math
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
li = lambda : list(input_())
pr = lambda x: print(x)
f = lambda : sys.stdout.flush()
n = int(input())
a = [i for i in range(n + 1)]
g = [[i] for i in range(n + 1)]
for _ in range(n - 1):
	(x, y) = il()
	(x, y) = (a[x], a[y])
	if len(g[x]) < len(g[y]):
		(x, y) = (y, x)
	g[x] += g[y]
	for i in g[y]:
		a[i] = x
print(*g[a[1]])


(n,) = map(int, input().split())
p = [i for i in range(0, n + 1)]
h = [1 for i in range(0, n + 1)]

def find(i):
	a = i
	while p[a] != a:
		a = p[a]
	p[i] = a
	h[i] = h[a] + 1
	return p[i]

def join(a, b):
	f_b = find(b)
	f_a = find(a)
	if h[f_a] > h[f_b]:
		p[f_b] = f_a
	else:
		p[f_a] = f_b
N = [-1 for i in range(0, n + 1)]

class List:

	def __init__(self, val):
		self.front = self
		self.value = val
		self.rear = self
		self.next = None

	def add(self, other):
		self.rear.next = other
		self.rear = other.rear
		other.front = self
m = {i: List(i) for i in range(1, n + 1)}

def printList(i):
	if i is None:
		return
	list = []
	while i != None:
		list.append(i.value)
		i = i.next
	print(str(list).replace(',', '').replace('[', '').replace(']', ''))
for i in range(1, n):
	(a, b) = map(int, input().split())
	m[find(a)].add(m[find(b)])
	temp = m[find(a)]
	del m[find(a)]
	del m[find(b)]
	join(a, b)
	key = find(a)
	m[key] = temp.front
try:
	printList(m[find(1)].front)
except RecursionError:
	pass


n = int(input())
d = dict()
point = dict()
l = []
for _ in range(n - 1):
	l += [list(map(int, input().split()))]

def get_point(nn):
	i = nn
	while not point[i] == i:
		i = point[i]
	return i
for pair in l:
	p0 = pair[0] in point.keys()
	p1 = pair[1] in point.keys()
	if not (p0 or p1):
		point[pair[1]] = pair[0]
		point[pair[0]] = pair[0]
		d[pair[0]] = [pair[0], pair[1]]
	elif p0 and (not p1):
		pp = get_point(pair[0])
		d[pp] += [pair[1]]
		point[pair[1]] = pp
	elif p1 and (not p0):
		pp = get_point(pair[1])
		d[pp] += [pair[0]]
		point[pair[0]] = pp
	else:
		pp1 = get_point(pair[1])
		pp0 = get_point(pair[0])
		d[pp0] += d[pp1]
		point[pp1] = pp0
print(' '.join(map(str, d[get_point(1)])))


n = int(input())
parent = [i for i in range(n)]
kitten = {}

def root(i):
	if parent[i] == i:
		return i
	else:
		parent[i] = root(parent[i])
		return parent[i]

def union(a, b):
	roota = root(a)
	rootb = root(b)
	if roota not in kitten:
		kitten[roota] = [roota]
	if rootb not in kitten:
		kitten[rootb] = [rootb]
	if len(kitten[roota]) >= len(kitten[rootb]):
		parent[rootb] = roota
		kitten[roota] += kitten[rootb]
		del kitten[rootb]
	else:
		parent[roota] = rootb
		kitten[rootb] += kitten[roota]
		del kitten[roota]
for i in range(n - 1):
	(x, y) = [int(s) - 1 for s in input().split(' ')]
	union(x, y)
print(' '.join([str(i + 1) for i in kitten[root(x)]]))


parent = {}
size = {}
cells = {}

def make_set(v):
	parent[v] = v
	size[v] = 1
	cells[v] = [v]

def find_set(v):
	if v == parent[v]:
		return v
	parent[v] = find_set(parent[v])
	return parent[v]

def union_sets(a, b):
	a = find_set(a)
	b = find_set(b)
	if a != b:
		if size[a] < size[b]:
			(a, b) = (b, a)
		parent[b] = a
		size[a] += size[b]
		cells[a] += cells[b]
n = input()
n = int(n)
for i in range(0, n):
	make_set(i + 1)
for i in range(0, n - 1):
	(a, b) = input().split()
	union_sets(int(a), int(b))
for i in cells[find_set(1)]:
	print(i, end=' ')
print(' ')


def get(x):
	if p[x] != x:
		p[x] = get(p[x])
	return p[x]

def union(x, y):
	(x, y) = (get(x), get(y))
	if r[x] > r[y]:
		(x, y) = (y, x)
	p[x] = y
	snm[y] += snm[x]
	snm[x].clear()
	if r[x] == r[y]:
		r[y] += 1
n = int(input())
p = [i for i in range(n + 1)]
r = [0 for _ in range(n + 1)]
snm = [[i] for i in range(n + 1)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	union(a, b)
for i in range(1, n + 1):
	if len(snm[i]) == n:
		print(*snm[i])
		break


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
p = list(range(n + 1))
c = [[i] for i in range(n + 1)]
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	(x, y) = (p[x], p[y])
	if len(c[x]) < len(c[y]):
		(x, y) = (y, x)
	c[x] += c[y]
	for z in c[y]:
		p[z] = x
print(*c[p[1]])


from sys import exit, setrecursionlimit
setrecursionlimit(10 ** 6)
inn = lambda : input().strip()
mapp = lambda : map(int, inn().split(' '))

class UF:

	def __init__(self, n):
		self.parent = [a for a in range(n)]
		self.array = [[a] for a in range(n)]

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a == b:
			return
		if len(self.array[b]) > len(self.array[a]):
			(a, b) = (b, a)
		self.parent[b] = a
		self.array[a] += self.array[b]

	def find(self, a):
		if self.parent[a] == a:
			return a
		self.parent[a] = self.find(self.parent[a])
		return self.parent[a]
N = int(inn())
uf = UF(N)
for _ in range(N - 1):
	(a, b) = mapp()
	(a, b) = (a - 1, b - 1)
	uf.union(a, b)
answer = None
for a in uf.array:
	if len(a) == N:
		answer = a
print(' '.join(map(lambda x: str(x + 1), answer)))


def procura(x):
	if pai[x] == x:
		return x
	else:
		return procura(pai[x])
n = int(input())
pai = [0] * (n + 1)
comp = [0] * (n + 1)
filhos = []
filhos.append([0])
for i in range(1, n + 1):
	pai[i] = i
	filhos.append([i])
	comp[i] = 1
for i in range(0, n - 1):
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	pa = procura(x)
	pb = procura(y)
	if comp[pa] < comp[pb]:
		temp = pa
		pa = pb
		pb = temp
	pai[pb] = pa
	comp[pa] = comp[pa] + comp[pb]
	comp[pb] = 0
	while len(filhos[pb]) > 0:
		filhos[pa].append(filhos[pb].pop())
u = procura(1)
while len(filhos[u]) > 0:
	print(str(filhos[u].pop()) + ' ', end='')


n = int(input())
ind_gr = list(range(n + 1))
gr = [[i] for i in range(n + 1)]
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	if len(gr[ind_gr[x]]) < len(gr[ind_gr[y]]):
		(ind_to, ind_from) = (ind_gr[y], ind_gr[x])
	else:
		(ind_to, ind_from) = (ind_gr[x], ind_gr[y])
	gr[ind_to] += gr[ind_from]
	for i in gr[ind_from]:
		ind_gr[i] = ind_to
print(*gr[ind_gr[1]])


n = int(input())
l = list(range(n + 1))
k = [[i] for i in range(n + 1)]
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	(x, y) = (l[x], l[y])
	if len(k[x]) < len(k[y]):
		(x, y) = (y, x)
	k[x] += k[y]
	for t in k[y]:
		l[t] = x
print(*k[l[1]])


import sys
input = sys.stdin.readline
n = int(input())
p = [list(map(int, input().split())) for i in range(n - 1)]
g = [i for i in range(n + 1)]

def find(x):
	while g[x] != x:
		x = g[x]
	return x

def union(x, y):
	if find(x) != find(y):
		g[find(x)] = g[find(y)] = min(find(x), find(y))
ans = [[i] for i in range(n + 1)]
for (i, j) in p:
	a = find(i)
	b = find(j)
	if b < a:
		ans[b] += ans[a]
	else:
		ans[a] += ans[b]
	union(i, j)
print(*ans[1])


n = int(input())
arr = []
for i in range(n - 1):
	arr.append(list(map(int, input().strip().split())))
mp = {}
ans = []
for i in range(n - 1):
	a = arr[i][0]
	b = arr[i][1]
	if a not in mp and b not in mp:
		mp[a] = len(ans)
		mp[b] = len(ans)
		ans.append([a, b])
	elif a in mp and b not in mp:
		ans[mp[a]].append(b)
		mp[b] = mp[a]
	elif a not in mp and b in mp:
		ans[mp[b]].append(a)
		mp[a] = mp[b]
	else:
		ans[mp[a]].extend(ans[mp[b]])
		for x in ans[mp[b]]:
			mp[x] = mp[a]
for i in range(len(ans)):
	if len(ans[i]) == n:
		print(*ans[i])
		break


import sys
lines = sys.stdin.read().split('\n')
lines.pop(-1)
n = int(lines.pop(0))

class Node:

	def __init__(self, id):
		self.id = id
		self.parent = self
		self.rank = 0
		self.size = 1

	def __repr__(self):
		return 'Node({!r})'.format(self.id)

def Find(x):
	if x.parent is not x:
		x.parent = Find(x.parent)
	return x.parent

def Union(x, y):
	xroot = Find(x)
	yroot = Find(y)
	if xroot is yroot:
		return
	if xroot.rank < yroot.rank:
		(xroot, yroot) = (yroot, xroot)
	yroot.parent = xroot
	xroot.size += yroot.size
	if xroot.rank == yroot.rank:
		xroot.rank = xroot.rank + 1
	paths[xroot.id] += paths[yroot.id]
nodos = [Node(i) for i in range(n + 1)]
paths = [[i] for i in range(n + 1)]
final = []
for line in lines:
	a = nodos[int(line.split(' ')[0])]
	b = nodos[int(line.split(' ')[1])]
	if Find(a) != Find(b):
		Union(a, b)
for i in paths[Find(nodos[1]).id]:
	print(i, end=' ')


n = int(input())
h = list(range(n + 1))
g = [[i] for i in range(n + 1)]
for i in range(n - 1):
	(x, y) = map(int, input().split())
	(x, y) = (h[x], h[y])
	if len(g[x]) < len(g[y]):
		(x, y) = (y, x)
	g[x] += g[y]
	for z in g[y]:
		h[z] = x
print(*g[h[1]])


import sys
import math
MAXN = 150001
parent = [None] * MAXN
rank = [0] * MAXN
lists = [None] * MAXN

def make_set(x):
	parent[x] = x
	lists[x] = [x]

def find_set(x):
	if parent[x] == x:
		return x
	parent[x] = find_set(parent[x])
	return parent[x]

def union(x, y):
	x = find_set(x)
	y = find_set(y)
	if x == y:
		return
	if rank[x] > rank[y]:
		parent[y] = x
		lists[x] += lists[y]
	else:
		parent[x] = y
		lists[y] += lists[x]
		if rank[x] == rank[y]:
			rank[y] += 1
n = int(input())
for x in range(1, n + 1):
	make_set(x)
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	union(x, y)
root = find_set(1)
result = lists[root]
print(' '.join(map(str, result)))


def find_parent(u):
	if par[u] != u:
		par[u] = find_parent(par[u])
	return par[u]
import sys
sys.setrecursionlimit(1000000)
n = int(input())
la = [[i + 1] for i in range(n)]

def union(a, b):
	(z1, z2) = (find_parent(a), find_parent(b))
	if z1 != z2:
		if len(la[z1 - 1]) > len(la[z2 - 1]):
			(z1, z2) = (z2, z1)
		for i in la[z1 - 1]:
			la[z2 - 1].append(i)
		par[z1] = z2
from collections import defaultdict
hash = defaultdict(list)
par = [0] + [i + 1 for i in range(n)]
bool = [False] * (n + 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	union(a, b)
z = find_parent(1)
for i in la[z - 1]:
	print(i, end=' ')


n = int(input())
g = {}
sets = {}
id = 1
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	ida = g.get(a)
	idb = g.get(b)
	if not ida and (not idb):
		sets[id] = [a, b]
		g[a] = id
		g[b] = id
	elif ida and (not idb):
		sets[ida].append(b)
		g[b] = ida
	elif idb and (not ida):
		sets[idb].append(a)
		g[a] = idb
	elif len(sets[ida]) > len(sets[idb]):
		for i in sets[idb]:
			g[i] = ida
		sets[ida] += sets.pop(idb)
	else:
		for i in sets[ida]:
			g[i] = idb
		sets[idb] += sets.pop(ida)
	id += 1
print(*sets[min(sets)])


import os
from io import BytesIO
nil = -1

class LL:

	def __init__(self, n):
		self.head = n
		self.tail = n

	def merge(self, other):
		self.tail.next = other.head
		other.head.prev = self.tail
		self.tail = other.tail

class LLNode:

	def __init__(self, value):
		self.prev = None
		self.next = None
		self.value = value

def solve(n, lst):

	def union(u, v):
		(p, q) = (find(u), find(v))
		if p == q:
			return
		ll[p].merge(ll[q])
		ll[q] = ll[p]
		if rank[p] < rank[q]:
			(p, q) = (q, p)
		if rank[p] == rank[q]:
			rank[p] += 1
		parent[q] = p

	def find(u):
		if parent[u] == nil:
			return u
		else:
			p = find(parent[u])
			parent[u] = p
			return p
	rank = [0] * n
	parent = [nil] * n
	ll = [LL(LLNode(i)) for i in range(n)]
	for (x, y) in lst:
		union(x, y)
	l = ll[find(0)]
	n = l.head
	out = []
	while True:
		out.append(str(n.value + 1))
		if n == l.tail:
			break
		n = n.next
	print(' '.join(out))

def solve_from_stdin():
	n = int(input())
	lst = []
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		lst.append((x - 1, y - 1))
	solve(n, lst)
solve_from_stdin()


import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

def main():
	n = int(input())
	uf = UnionFind(n + 1)
	res = [[i] for i in range(n + 1)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		(ind_x, ind_y) = (uf.find(x), uf.find(y))
		uf.merge(x, y)
		new_ind = uf.find(x)
		res[new_ind].extend(res[ind_y] if new_ind == ind_x else res[ind_x])
	os.write(1, ' '.join(map(str, max(res, key=len))).encode())
main()


from sys import stdin, stdout
from itertools import combinations
from collections import defaultdict, OrderedDict
import math
import heapq

def listIn():
	return list(map(int, stdin.readline().strip().split()))

def stringListIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())

def stringIn():
	return stdin.readline().strip()

class DSU:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.arr_size = [1] * (n + 1)
		self.arr = [[i] for i in range(n + 1)]

	def find_root(self, x):
		temp = x
		while temp != self.parent[temp]:
			temp = self.parent[temp]
		return temp

	def find(self, x, y):
		if find_root[x] == find_root[y]:
			return True
		else:
			return False

	def union(self, x, y):
		root_x = self.find_root(x)
		root_y = self.find_root(y)
		if root_x == root_y:
			return False
		if self.arr_size[root_x] < self.arr_size[root_y]:
			self.parent[root_x] = self.parent[root_y]
			self.arr_size[root_y] += self.arr_size[root_x]
			self.arr[root_y] += self.arr[root_x]
		else:
			self.parent[root_y] = self.parent[root_x]
			self.arr_size[root_x] += self.arr_size[root_y]
			self.arr[root_x] += self.arr[root_y]
n = intIn()
dsu = DSU(n)
for i in range(n - 1):
	(x, y) = listIn()
	dsu.union(x, y)
ans = []
for i in range(1, n + 1):
	if dsu.arr_size[i] == n:
		ans = dsu.arr[i]
print(*ans)


n = int(input())
p = [i for i in range(1, n + 1)]
l = [[i] for i in range(n + 1)]
p = [0] + p
size = [1] * (n + 1)

def get(a):
	if p[a] != a:
		p[a] = get(p[a])
	return p[a]

def union(a, b):
	a = get(a)
	b = get(b)
	if size[a] > size[b]:
		(a, b) = (b, a)
	l[b] += l[a]
	p[a] = b
	size[b] += size[a]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	if get(a) != get(b):
		union(a, b)
w = get(1)
print(*l[w], sep=' ')


nxt = []
last = []
rt = []

def dsu(n):
	for i in range(0, n + 1):
		rt.append(-1)
		last.append(i)
		nxt.append(-1)

def root(x):
	if rt[x] < 0:
		return x
	else:
		rt[x] = root(rt[x])
		return rt[x]

def union(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		rt[x] = rt[x] + rt[y]
		rt[y] = x
		nxt[last[x]] = y
		last[x] = last[y]
n = int(input())
dsu(n)
for z in range(n - 1):
	(x, y) = [int(i) for i in input().split()]
	union(x, y)
i = root(1)
while i != -1:
	print(i, end=' ')
	i = nxt[i]


class Solution:

	def __init__(self, n: int) -> None:
		self.makeSet(n)

	def makeSet(self, n: int) -> None:
		self.dsuParent = list(range(n + 1))
		self.dsuSize = [1 for i in range(n + 1)]
		self.dsuRepr = [[i] for i in range(n + 1)]

	def findSet(self, v: int) -> int:
		if v == self.dsuParent[v]:
			return v
		self.dsuParent[v] = self.findSet(self.dsuParent[v])
		return self.dsuParent[v]

	def unionSet(self, u: int, v: int) -> None:
		pu = self.findSet(u)
		pv = self.findSet(v)
		if pu != pv:
			if self.dsuSize[pu] >= self.dsuSize[pv]:
				self.dsuParent[pv] = pu
				self.dsuSize[pu] += self.dsuSize[pv]
				self.dsuRepr[pu].extend(self.dsuRepr[pv])
			else:
				self.dsuParent[pu] = pv
				self.dsuSize[pv] += self.dsuSize[pu]
				self.dsuRepr[pv].extend(self.dsuRepr[pu])
n = int(input())
sol = Solution(n)
for i in range(1, n):
	(u, v) = map(int, input().strip().split())
	sol.unionSet(u, v)
print(' '.join(map(str, sol.dsuRepr[sol.findSet(1)])))