One day Bob got a letter in an envelope. Bob knows that when Berland's post officers send a letter directly from city «A» to city «B», they stamp it with «A B», or «B A». Unfortunately, often it is impossible to send a letter directly from the city of the sender to the city of the receiver, that's why the letter is sent via some intermediate cities. Post officers never send a letter in such a way that the route of this letter contains some city more than once. Bob is sure that the post officers stamp the letters accurately.

There are n stamps on the envelope of Bob's letter. He understands that the possible routes of this letter are only two. But the stamps are numerous, and Bob can't determine himself none of these routes. That's why he asks you to help him. Find one of the possible routes of the letter.

Input

The first line contains integer n (1 ≤ n ≤ 105) — amount of mail stamps on the envelope. Then there follow n lines with two integers each — description of the stamps. Each stamp is described with indexes of the cities between which a letter is sent. The indexes of cities are integers from 1 to 109. Indexes of all the cities are different. Every time the letter is sent from one city to another, exactly one stamp is put on the envelope. It is guaranteed that the given stamps correspond to some valid route from some city to some other city. 

Output

Output n + 1 numbers — indexes of cities in one of the two possible routes of the letter.

Examples

Input

2
1 100
100 2


Output

2 100 1 

Input

3
3 1
100 2
3 2


Output

100 2 3 1

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Graph traversal

Implementation
Skill types: Data structures

Starter code:

Solutions:
n = int(input())
d = {}
for i in range(n):
	(a, b) = map(int, input().split())
	if a in d:
		d[a].append(b)
	else:
		d[a] = [b]
	if b in d:
		d[b].append(a)
	else:
		d[b] = [a]
ans = []
for el in d:
	if len(d[el]) == 1:
		ans.append(el)
		root = el
		break
cur = root
while True:
	for el in d[cur]:
		if el == ans[-1]:
			continue
		if cur != root:
			ans.append(cur)
		cur = el
		break
	if len(d[cur]) == 1:
		ans.append(cur)
		break
print(*ans)


from collections import defaultdict
from typing import List, Tuple

def solve(n: int, stamps: List[Tuple[int, int]]) -> str:
	visited = set()
	graph = defaultdict(list)
	path = []
	for (u, v) in stamps:
		graph[u].append(v)
		graph[v].append(u)
	start = [node for node in graph if len(graph[node]) == 1][0]
	stack = [start]
	while stack:
		curr = stack.pop()
		visited.add(curr)
		path.append(curr)
		for adj_node in graph[curr]:
			if adj_node not in visited:
				stack.append(adj_node)
	return ' '.join(map(str, path))
n = int(input())
stamps = [tuple(map(int, input().split())) for _ in range(n)]
print(solve(n, stamps))


n = int(input())
tree = {}
for x in range(n):
	arr = input().split()
	arr[0] = int(arr[0])
	arr[1] = int(arr[1])
	if arr[0] in tree:
		tree[arr[0]].append(arr[1])
	else:
		tree[arr[0]] = [arr[1]]
	if arr[1] in tree:
		tree[arr[1]].append(arr[0])
	else:
		tree[arr[1]] = [arr[0]]
for x in tree:
	if len(tree[x]) == 1:
		print(x, end=' ')
		nex = tree[x][0]
		pre = x
		while len(tree[nex]) == 2:
			print(nex, end=' ')
			if tree[nex][0] != pre:
				(pre, nex) = (nex, tree[nex][0])
			else:
				assert pre == tree[nex][0]
				(pre, nex) = (nex, tree[nex][1])
		print(nex)
		break


n = int(input())
edges = {}
for _ in range(n):
	(a, b) = map(int, input().split())
	if a in edges:
		edges[a] += [b]
	else:
		edges[a] = [b]
	if b in edges:
		edges[b] += [a]
	else:
		edges[b] = [a]
route = []
for (key, val) in edges.items():
	route = [key, val[0]]
	break
while len(route) < n + 1:
	if len(edges[route[-1]]) == 1:
		route.reverse()
	elif edges[route[-1]][0] == route[-2]:
		route += [edges[route[-1]][1]]
	else:
		route += [edges[route[-1]][0]]
print(' '.join(map(str, route)))


n = int(input())
d = dict()
for _ in range(n):
	line = input().split(' ')
	a = int(line[0])
	b = int(line[1])
	if a in d:
		d[a].append(b)
	else:
		d[a] = [b]
	if b in d:
		d[b].append(a)
	else:
		d[b] = [a]
end_cities = list()
for x in d:
	if len(d[x]) == 1:
		end_cities.append(x)
prev_city = end_cities[0]
next_city = d[prev_city][0]
print(prev_city, end=' ')
while True:
	print(next_city, end=' ')
	if next_city == end_cities[1]:
		break
	d[next_city].remove(prev_city)
	prev_city = next_city
	next_city = d[next_city][0]


from collections import *
(d, c) = (defaultdict(int), [])
for i in range(int(input())):
	(x, y) = map(int, input().split())
	c += [x, y]
	d[x] += y
	d[y] += x
(a, b) = [q for (q, k) in Counter(c).items() if k == 1]
q = 0
while a != b:
	print(a)
	(q, a) = (a, d[a] - q)
print(a)


import sys

def solve():
	n = int(input())
	once = set()
	mapsto = dict()
	for i in range(n):
		(a, b) = map(int, input().split())
		spadd(once, a)
		spadd(once, b)
		dictadd(mapsto, a, b)
		dictadd(mapsto, b, a)
	prev = -1
	cur = once.pop()
	res = [cur]
	for i in range(n):
		pos = mapsto[cur]
		nxt = pos[0] if pos[0] != prev else pos[1]
		res.append(nxt)
		prev = cur
		cur = nxt
	print(' '.join(map(str, res)))

def spadd(s, val):
	if val in s:
		s.remove(val)
	else:
		s.add(val)

def dictadd(d, key, val):
	if key in d:
		d[key].append(val)
	else:
		d[key] = [val]

def prt(l):
	return print(''.join(l))

def rv():
	return map(int, input().split())

def rl(n):
	return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


dic = {}
for notused in range(int(input())):
	(i1, i2) = list(map(int, input().split(' ')))
	if i1 in dic:
		dic[i1].append(i2)
	else:
		dic[i1] = [i2]
	if i2 in dic:
		dic[i2].append(i1)
	else:
		dic[i2] = [i1]
(start, end) = (-1, -1)
for key in dic.keys():
	if len(dic[key]) == 1:
		if start == -1:
			start = key
		else:
			end = key
seq = start
prev = -1
print(seq, end=' ')
while seq != end:
	arr = dic[seq]
	if arr[0] != prev:
		temp = arr[0]
	else:
		temp = arr[1]
	(prev, seq) = (seq, temp)
	print(seq, end=' ')
print()


dict_route = {}
cnt = int(input('').strip())
for i in range(cnt):
	peer = input('').strip().split()
	for p in peer:
		if not dict_route.get(p):
			dict_route[p] = []
		peer_copy = peer.copy()
		peer_copy.remove(p)
		dict_route[p] += peer_copy
start_end_keys = []
for (key, val) in dict_route.items():
	if len(val) == 1:
		start_end_keys.append(key)
start_key = start_end_keys[-1]
end_key = start_end_keys[0]
possible_routes = []
while True:
	possible_routes.append(start_key)
	if start_key == end_key:
		break
	next_key = dict_route[start_key][0]
	dict_route[next_key].remove(start_key)
	start_key = next_key
print(' '.join(possible_routes))


not_visited = dict()
n = int(input())
Graph = {}
vertices = set()
for i in range(n):
	input_ = [int(i) for i in input().split(' ')]
	vertices.add(input_[0])
	vertices.add(input_[1])
	if input_[0] in Graph:
		Graph[input_[0]].append(input_[1])
		not_visited[input_[0]] = 2
	else:
		Graph[input_[0]] = [input_[1]]
		not_visited[input_[0]] = 1
	if input_[1] in Graph:
		Graph[input_[1]].append(input_[0])
		not_visited[input_[1]] = 2
	else:
		Graph[input_[1]] = [input_[0]]
		not_visited[input_[1]] = 1
for vertice in vertices:
	if not_visited[vertice] == 1:
		vertice_begin = vertice
		break
answer = []
answer.append(vertice_begin)
curr = Graph[vertice_begin][0]
answer.append(curr)
not_visited[vertice_begin] = 0
not_visited[curr] = 0
while len(Graph[curr]) > 1:
	for i in range(len(Graph[curr])):
		if not_visited[Graph[curr][i]] != 0:
			curr_ = Graph[curr][i]
	answer.append(curr_)
	not_visited[curr_] = 0
	curr = curr_
print(' '.join([str(i) for i in answer]))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	r = {}
	for i in range(n):
		(a, b) = [int(x) for x in input().split(' ')]
		if a in r:
			r[a].append(b)
		else:
			r[a] = [b]
		if b in r:
			r[b].append(a)
		else:
			r[b] = [a]
	for x in r:
		if len(r[x]) == 1:
			v = x
			break
	p = [v]
	visited = set([v])
	v = r[v][0]
	p.append(v)
	visited.add(v)
	while True:
		if len(r[v]) == 1:
			break
		else:
			if r[v][1] in visited:
				v = r[v][0]
			else:
				v = r[v][1]
			p.append(v)
			visited.add(v)
	return p
print(*solve())


import sys
from collections import deque
input = sys.stdin.readline
g = {}
v = set()
for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	if a in v:
		v.remove(a)
	else:
		v.add(a)
	if b in v:
		v.remove(b)
	else:
		v.add(b)
	if a in g:
		g[a].append(b)
	else:
		g[a] = [b]
	if b in g:
		g[b].append(a)
	else:
		g[b] = [a]
ans = []
for i in v:
	q = deque([[i, -1]])
	while q:
		(curr, par) = q.popleft()
		ans.append(curr)
		for i in g[curr]:
			if i != par:
				q.append([i, curr])
	break
print(*ans)


n = int(input())
d = {}
from sys import stdin
for i in range(n):
	(a, b) = map(int, input().split())
	if d.get(a) == None:
		d[a] = []
	if d.get(b) == None:
		d[b] = []
	d[a].append(b)
	d[b].append(a)
for (i, item) in enumerate(d):
	if len(d[item]) == 1:
		break
res = [item]
prev = item
item = d[item][0]
for i in range(n - 1):
	res.append(item)
	(x, y) = (d[item][0], d[item][1])
	if x == prev:
		prev = item
		item = y
	else:
		prev = item
		item = x
res.append(item)
print(*res)


from collections import defaultdict, Counter

class Solution:

	def __init__(self):
		pass

	def solve_and_print(self):
		(d, c) = (defaultdict(int), [])
		for _ in range(int(input())):
			(x, y) = [int(x) for x in input().split()]
			c += [x, y]
			d[x] += y
			d[y] += x
		(a, b) = [q for (q, k) in Counter(c).items() if k == 1]
		q = 0
		while a != b:
			print(a, end=' ')
			(q, a) = (a, d[a] - q)
		print(a, end=' ')
Solution().solve_and_print()


import sys
from array import array
from collections import defaultdict

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
n = int(input())
adj = defaultdict(list)
deg = defaultdict(int)
for _ in range(n):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
	deg[u] += 1
	deg[v] += 1
v = -1
for (key, val) in deg.items():
	if val == 1:
		v = key
		break
ans = []
while True:
	ans.append(v)
	deg[v] = 0
	for dest in adj[v]:
		if deg[dest]:
			deg[dest] = 0
			v = dest
			break
	else:
		break
print(*ans)


(d1, d2, d3) = ({}, {}, {})
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	if a in d1.keys():
		d1[a] += 1
	else:
		d1[a] = 1
	if b in d1.keys():
		d1[b] += 1
	else:
		d1[b] = 1
	if a in d2.keys():
		d3[a] = b
	else:
		d2[a] = b
	if b in d2.keys():
		d3[b] = a
	else:
		d2[b] = a
(first, last) = (0, 0)
for i in d1.keys():
	if d1[i] == 1:
		if first == 0:
			first = i
		else:
			last = i
ans = [first]
i = first
cont = 0
while i != last:
	if i in d2.keys() and d2[i] != cont:
		ans.append(d2[i])
		cont = i
		i = d2[i]
	elif i in d3.keys() and d3[i] != cont:
		ans.append(d3[i])
		cont = i
		i = d3[i]
print(*ans, sep=' ')


n = int(input())
p = [0] * n
(d, t) = ({}, {})
for i in range(n):
	for x in map(int, input().split()):
		(t[x], d[x]) = (0, d[x] + i) if x in d else (1, i)
		p[i] += x
(x, q) = (y for y in t if t[y])
s = [x]
while x != q:
	y = p[d[x]] - x
	s += [y]
	d[y] -= d[x]
	x = y
for q in s:
	print(q)


import os
import sys
from io import BytesIO, IOBase
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())
d = dict()
a = []
for j in range(n):
	(x, y) = map(int, input().split())
	if x in d.keys():
		d[x].append(y)
	else:
		a.append(x)
		d[x] = [y]
	if y in d.keys():
		d[y].append(x)
	else:
		a.append(y)
		d[y] = [x]
r = len(a)
for j in range(r):
	if len(d[a[j]]) == 1:
		k = a[j]
		break
c = []
s = [k]
v = dict()
while s:
	p = s.pop()
	v[p] = 1
	c.append(p)
	if p != k and len(d[p]) == 1:
		break
	if d[p][0] in v.keys():
		s.append(d[p][1])
	else:
		s.append(d[p][0])
print(*c)