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: interview

Starter code:

Solutions:
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=" ")
        



n = int(input())
# 2<=n<=150.000
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))
#heapq.heapify(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)

# -*- coding: utf-8 -*-
# @Time    : 2019/2/23 19:02
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : F. Asya And Kittens.py


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()))
        # print(x, y)
        uf.union(x, y)
    x = uf.find(1)
    print(*uf.data[x])


def __starting_point():
    main()

__starting_point()

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)


n = int(input())

arr = []

for i in range(n-1):
    arr.append(list(map(int,input().strip().split())))
mp = {}

ans = []
#print(arr)
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])
    else:
        if (a in mp) and (b not in mp):
            ans[mp[a]].append(b)
            mp[b]= mp[a]
        else:
            if (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












n=int(input())
d={}
for i in range(n-1):
    a,b=list(map(int,input().split()))
    if (a not in list(d.keys())) and (b not in list(d.keys())):
        d[a]=[a,b]
        d[b]=d[a]
    elif (a in list(d.keys())) and (b not in list(d.keys())):
        d[a]+=[b]
        d[b]=d[a]
    elif (a not in list(d.keys())) and (b in list(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())

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:
        #print("x1")
        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:
        #print("x2")
        d[a].s.append(b)
        d[b] = d[a]
    elif a not in d and b in d:
        #print("x3")
        d[b].s.append(a)
        d[a] = d[b]
    else:
        #print("x4")
        d[a].s.extend(d[b].s)
        for x in d[b].s:
            d[x] = d[a]
    #ppp(d)

print(*d[1].s)



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()

"""
5
1 4
2 5
3 1
4 5
"""

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 list(point.keys())
    p1 = pair[1] in list(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)])))



# -*- coding: utf-8 -*-
# @Date    : 2019-02-23 15:15:00
# @Author  : raj lath (oorja.halt@gmail.com)
# @Link    : link
# @Version : 1.0.0

from sys import stdin

max_val=int(10e12)
min_val=int(-10e12)

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)



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 = list(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:
    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 x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        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)
        # Make an edge from the root of lower tree to the root of higher tree
        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 the height of tree the tree is the same, increase one of the heights by 1
            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)


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 x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        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)
        # Make an edge from the root of lower tree to the root of higher tree
        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 the height of tree the tree is the same, increase one of the heights by 1
            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)


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)]]))

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]])

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))


n = int(input())

# 要素iの親（マージ先）を指す
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())
    # xのマージ先の配列の要素数 >= yのマージ先の配列の要素数となるようにxとyを入れ替える（マージテクの前処理）
    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]])

n = int(input())

# 要素iの親（マージ先）を指す
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())
    
    # xのマージ先の配列の要素数 >= yのマージ先の配列の要素数となるようにxとyを入れ替える（マージテクの前処理）
    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]])

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]])))

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)
# print(ds.rank)
# print(ds.parent)
ans = ds.ls[ds.find(1)]
for a in ans:
    print(a, end=" ")


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)
        rank = self.rank
        parent = self.parent
        ls = self.ls

        if rank[node] > rank[other]:
            parent[other] = node
            ls[node].extend(ls[other])

        elif rank[other] > rank[node]:
            parent[node] = other
            ls[other].extend(ls[node])

        else:
            parent[other] = node
            ls[node] += ls[other]
            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(ds.rank)
# print(ds.parent)
ans = ds.ls[ds.find(1)]
for a in ans:
    print(a, end=" ")