There are $n$ kids, numbered from $1$ to $n$, dancing in a circle around the Christmas tree. Let's enumerate them in a clockwise direction as $p_1$, $p_2$, ..., $p_n$ (all these numbers are from $1$ to $n$ and are distinct, so $p$ is a permutation). Let the next kid for a kid $p_i$ be kid $p_{i + 1}$ if $i < n$ and $p_1$ otherwise. After the dance, each kid remembered two kids: the next kid (let's call him $x$) and the next kid for $x$. Each kid told you which kids he/she remembered: the kid $i$ remembered kids $a_{i, 1}$ and $a_{i, 2}$. However, the order of $a_{i, 1}$ and $a_{i, 2}$ can differ from their order in the circle. [Image] Example: 5 kids in a circle, $p=[3, 2, 4, 1, 5]$ (or any cyclic shift). The information kids remembered is: $a_{1,1}=3$, $a_{1,2}=5$; $a_{2,1}=1$, $a_{2,2}=4$; $a_{3,1}=2$, $a_{3,2}=4$; $a_{4,1}=1$, $a_{4,2}=5$; $a_{5,1}=2$, $a_{5,2}=3$. 

You have to restore the order of the kids in the circle using this information. If there are several answers, you may print any. It is guaranteed that at least one solution exists.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of the kids.

The next $n$ lines contain $2$ integers each. The $i$-th line contains two integers $a_{i, 1}$ and $a_{i, 2}$ ($1 \le a_{i, 1}, a_{i, 2} \le n, a_{i, 1} \ne a_{i, 2}$) — the kids the $i$-th kid remembered, given in arbitrary order.


-----Output-----

Print $n$ integers $p_1$, $p_2$, ..., $p_n$ — permutation of integers from $1$ to $n$, which corresponds to the order of kids in the circle. If there are several answers, you may print any (for example, it doesn't matter which kid is the first in the circle). It is guaranteed that at least one solution exists.


-----Examples-----
Input
5
3 5
1 4
2 4
1 5
2 3

Output
3 2 4 1 5 

Input
3
2 3
3 1
1 2

Output
3 1 2

Difficulty: introductory

Starter code:

Solutions:
n = int(input())

A = [-1]
ans = [1]

for i in range(n):
    A.append(tuple(map(int, input().split())))

a = A[1][0]
b = A[1][1]

c = A[a][0]
d = A[a][1]

if b == c or b == d:
    ans.append(a)
    ans.append(b)
else:
    ans.append(b)
    ans.append(a)

while len(ans) != n:
    p = A[ans[-2]]
    
    if p[0] == ans[-1]:
        ans.append(p[1])
    else:
        ans.append(p[0])

for i in ans:
    print(i, end=' ')

from sys import stdin
n=int(stdin.readline().strip())
if n==3:
    print("1 2 3")
    return
adj=[(0,0)]

for i in range(n):
    a,b=list(map(int,stdin.readline().strip().split()))
    adj.append((a,b))
s=[]
x=1

while len(s)<n:
    if adj[x][0] in adj[adj[x][1]]:
        s.append(adj[x][1])
        s.append(adj[x][0])
        x=adj[x][0]
    if adj[x][1] in adj[adj[x][0]]:
        s.append(adj[x][0])
        s.append(adj[x][1])
        x=adj[x][1]
print(*s[0:n])


def read_nums():
    return [int(x) for x in input().split()]


def main():
    n, = read_nums()
    d = {}
    for i in range(1, n + 1):
        d[i] = read_nums()

    circle = {1: d[1][0] if d[1][1] in d[d[1][0]] else d[1][1]}

    prev = 1
    cur = circle[1]
    while cur != 1:
        circle[cur] = list(set(d[prev]) & set(d[cur]))[0]
        prev = cur
        cur = circle[cur]

    nums = [1]
    cur = circle[1]
    while cur != 1:
        nums.append(cur)
        cur = circle[cur]
    print(' '.join([str(x) for x in nums]))


def __starting_point():
    main()

__starting_point()

import math
import bisect
import itertools
import sys
I=lambda : sys.stdin.readline()
mod=10**9 +7
'''fact=[1]*100001
ifact=[1]*100001
for i in range(1,100001):
    fact[i]=((fact[i-1])*i)%mod
    ifact[i]=((ifact[i-1])*pow(i,mod-2,mod))%mod
def ncr(n,r):
    return (((fact[n]*ifact[n-r])%mod)*ifact[r])%mod
def npr(n,r):
    return (((fact[n]*ifact[n-r])%mod))
    '''


def mindiff(a):
    b=a[:]
    b.sort()
    m=10000000000
    for i in range(len(b)-1):
        if b[i+1]-b[i]<m:
            m=b[i+1]-b[i]
    return m
    
def lcm(a,b):
    return a*b//math.gcd(a,b)

    
def merge(a,b):
    i=0;j=0
    c=0
    ans=[]
    while i<len(a) and j<len(b):
        if a[i]<b[j]:
            ans.append(a[i])
            i+=1
        else:
            ans.append(b[j])
            c+=len(a)-i
            j+=1
    ans+=a[i:]
    ans+=b[j:]
    return ans,c
def mergesort(a):
    if len(a)==1:
        return a,0
    mid=len(a)//2   
    left,left_inversion=mergesort(a[:mid])
    right,right_inversion=mergesort(a[mid:])
    m,c=merge(left,right)
    c+=(left_inversion+right_inversion)
    return m,c
    
def is_prime(num):
    if num == 1: return False
    if num == 2: return True
    if num == 3: return True
    if num%2 == 0: return False
    if num%3 == 0: return False
    t = 5
    a = 2
    while t <= int(math.sqrt(num)):
        if num%t == 0: return False
        t += a
        a = 6 - a
    return True
    
  
def ceil(a,b):
    if a%b==0:
        return a//b
    else:
        return (a//b + 1)

def binsearch(arr,b,low,high):
    if low==high:
        return low
    if arr[math.ceil((low+high)/2)]<b:
        return binsearch(arr,b,low,math.ceil((low+high)/2) -1 )
    else:
        return binsearch(arr,b,math.ceil((low+high)/2),high)
def ncr1(n,r):
    s=1
    for i in range(min(n-r,r)):
        s*=(n-i)
        s%=mod
        s*=pow(i+1,mod-2,mod)
        s%=mod
    return s
    
def calc(n,m,r):
    s=0
    for i in range(0,r+1,2):
        s+=ncr1(n,i)*ncr1(m,i)
        s%=mod
    return s    
        
        

#/////////////////////////////////////////////////////////////////////////////////////////////////
n=int(input())
d={}
for i in range(1,n+1):
    x,y=map(int,input().split())
    d[i]=[x,y]
d1={}    
if n==3:
    print(1,2,3);return
    
for i in range(1,n+1):
    if d[i][0] in d[d[i][1]]:
        d1[i]=d[i][1]
    else:
        d1[i]=d[i][0]
k=d1[1]

for i in range(n):
    print(k,end=' ')
    k=d1[k]
    

# alpha = "abcdefghijklmnopqrstuvwxyz"
t = 1
from heapq import heappop, heappush
for test in range(t):
    n = int(input())
    # a = list(map(int, input().split()))
    D = {}
    for i in range(1, n+1):
        a,b = list(map(int, input().split()))
        D[i] = [a,b]

    if n==3:
        ans=(1,2,3)
    else:
        ans=[1]    
        a,b = D[1]
        if a in D[b]:
            ans.append(b)
            ans.append(a)
        else:
            ans.append(a)
            ans.append(b)
        
        while len(ans)<n:  
            a,b = D[ans[-2]]
            if ans[-1]==a:
                ans.append(b)
            else:
                ans.append(a)
    print(*ans)
        
   




n = int( input() )
m = [[0 for i in range(2)] for j in range(n)]
for k in range(n):
	m[k][0],m[k][1] = map(lambda x: int(x)-1,input().split())
l=list()
l.append(0)
if(m[0][0] in m[m[0][1]]):
	l.append(m[0][1])
	l.append(m[0][0])
else:
	l.append(m[0][0])
	l.append(m[0][1])
cpt = 2
while( l[-1] != l[0]):
	if( m[l[-2]][0] == l[-1] ):
		l.append(m[l[-2]][1])
	else:
		l.append(m[l[-2]][0])
print(" ".join(map(lambda x : str(x+1),l[:len(l)-1])))

import sys
n=int(sys.stdin.readline())
l=[]
dct={}
for i in range(n):
    x=list(map(int,sys.stdin.readline().split()))
    dct[str(x)]=0
    l.append(x)
this=1
nxt=-1
nxt2nxt=-1
x,y=l[0][0],l[0][1]
if str([1,y]) in dct or str([y,1]) in dct:
    nxt=y
    nxt2nxt=x
else:
    nxt=x
    nxt2nxt=y
for i in range(n):
    sys.stdout.write(str(this)+" ")
    this=nxt
    nxt=nxt2nxt
    if(l[this-1][0]==nxt):
        nxt2nxt=l[this-1][1]
    else:
        nxt2nxt=l[this-1][0]

n=int(input())
p=[]
for i in range(n):
	x,y=map(int,input().split())
	p.append([x-1,y-1])
ans=[]
k=0
i=0
#print(p)
while 1:
	#print(i,p[i][0],p[i][1])
	#print(p[p[i][0]],p[p[i][1]])
	if p[i][0] in p[p[i][1]]:
		ans+=[i,p[i][1]]
		i = p[i][0]
	else:
		ans += [i,p[i][0]]
		i=p[i][1]
	#print(ans,i)
	k+=2
	if k>=n:
		break
#print(ans)
for i in range(n):
	print(ans[i]+1,end=" ")


n = int(input())
sosed = dict()
for c in range(n):
    sosed[c+1] = set()
z1, z2 = map(int, input().split())
sosed[z1].add(z2)
sosed[z2].add(z1)
i = [z1, z2]
for __ in range(1, n):
    z1, z2 = map(int, input().split())
    sosed[z1].add(z2)
    sosed[z2].add(z1)
    if z1 == 1 or z2 == 1:
        if max(z1, z2) in i:
            i = [max(z1, z2)]
pred = set()
cnt = 0
i = i[0]
print(1, end=" ")
pred.add(1)
while cnt < n-1:
    cnt += 1
    print(i, end=" ")
    pred.add(i)
    for y in sosed[i]:
        if y not in pred:
            i = y


n = int(input())

v = {}

for i in range(1, n + 1):
    v[i] = set(map(int, input().split()))

ans = []

ans_s = set()

ans.append(1)

ans_s.add(1)

while len(ans) < n:
    for i in v[ans[-1]]:
        if len(v[i].intersection(v[ans[-1]])) > 0 and i not in ans_s:
            ans.append(i)
            ans_s.add(i)
            break


print(" ".join(map(str, ans)))

n=int(input())
mas=[]
itog=[]
for i in range(n):
    a=list(map(int,input().split()))
    mas.append(a)
itog.append(1)
p=0
while len(itog)<n-1:
    if (mas[p][1] in mas[mas[p][0]-1]):
        itog.append(mas[p][0])
        p=mas[p][0]-1
    else:
        itog.append(mas[p][1])
        p=mas[p][1]-1
        
if (mas[p][1] in mas[mas[p][0]-1]) and not(mas[p][0] in itog):
    itog.append(mas[p][0])
    p=mas[p][0]-1
else:
    itog.append(mas[p][1])
    p=mas[p][1]-1
    
for i in itog:
    print(i,end=" ")


n = int(input())
d = []
for i in range(n):
    x = input().split()
    d.append([int(x[0]) - 1, int(x[1]) - 1])
first = d[0][0]
second = d[0][1]
if (d[first][0] != second and d[first][1] != second):
    t = first;
    first = second
    second = t
ans = [1, first + 1]
nex = second
while (nex != 0):
    ans.append(nex + 1)
    if (d[first][0] == second):
        nex = d[first][1]
    else:
        nex = d[first][0]
    first = second
    second = nex
for i in ans:
    print(i, end=" ")

def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())

n = ii()
if n == 3:
    ans = [1, 2, 3]
else:
    a = [None] + [li() for i in range(n)]
    ans = []
    i = 1
    while 1:
        ans.append(i)
        j = a[i][0]
        if a[i][1] not in a[j]:
            j = a[i][1]
        i = j
        if i == 1: break
print(*ans)


n = int(input())
L = []
for _ in range(n):
    x,y = [int(x)-1 for x in input().split()]
    L.append((x,y))

if n == 3:
    print('1 2 3')
else:
    order = ['1']
    count = 1
    current = 0
    while count < n:
        a,b = L[current]
        if b in L[a]:
            order.append(str(a+1))
            count += 1
            current = a
        else:
            order.append(str(b+1))
            count += 1
            current = b
    print(' '.join(order))


n = int(input())
g = {i: set() for i in range(1, n + 1)}
d = {i: set() for i in range(1, n + 1)}

for i in range(1, n + 1):
    x, y = list(map(int, input().split()))
    g[x].add(y)
    g[y].add(x)
    d[i].add(x)
    d[i].add(y)

a = [1]
b = set(a)
i = 1
c = 0
while c < n:
    x = g[i]
    y = d[i]
    for j in y:
        if j in x and j not in b:
            a.append(j)
            b.add(j)
            i = j
            break
    c += 1
print(*a)


n = int(input())
d = {}
for i in range(1, n + 1):
    d[i] = [*map(int, input().split())]

u = n - 1
c1 = 1
a, b = d[c1]
if b in d[a]:
    c2 = a
else:
    c2 = b


p = lambda x: print(x, end=' ')

p(c1)
while u > 0:
    p(c2)
    (c3,) = set(d[c1]).intersection(set(d[c2]))
    c2, c1 = c3, c2
    u -= 1

n = int(input())
a = [[0, 0]]
ans = [1]
for i in range(n):
    a.append([int(x) for x in input().split()])
    
options  = a[1]
ans.append(options[0])
ans.append(options[1])

if ans[-1] not in a[ans[-2]]:
    ans[1], ans[2] = ans[2], ans[1]


for i in range(1, n - 1):
    
    options = a[ans[i]]
    #print('We are at', ans[i], options, ans)
    idx = options.index(ans[-1])
    rem = options[1 - idx]
    ans.append(rem)

print(*ans[:-1])
    


n = int(input())
d = {}
sees = []
for _ in range(n):
    a, b = map(int, input().split())
    if a not in d:
        d[a] = set()
    if b not in d:
        d[b] = set()
    d[a].add(b)
    d[b].add(a)
    sees.append(set((a, b)))
res = []
if b in sees[a-1]:
    res.extend([a, b])
    d[b].remove(a)
else:
    res.extend([b, a])
    d[a].remove(b)
for _ in range(n-2):
    last = res[-1]
    nex = d[last].pop()
    d[nex].remove(last)
    res.append(nex)
for r in res:
    print(r, end=' ')
print()


import sys
input = sys.stdin.readline

n=int(input())
P=[list(map(int,input().split())) for i in range(n)]

x,y=P[0]

if y in P[x-1]:
    print(1,x,end=" ")
    n=x
    nn=y
else:
    print(1,y,end=" ")
    n=y
    nn=x

while nn!=1:
    k,u=P[n-1]
    print(nn,end=" ")
    if k==nn:
        n,nn=nn,u
    else:
        n,nn=nn,k
    


def func():
    n = int(input())
    g = [()] + [set(map(int, input().split())) for i in range(n)]
    # print(g)
    if n == 3:
        print(1, 2, 3)
        return None

    xor = [1]
    for i in range(n-1):
        # print(xor)
        x, y = (j for j in g[xor[-1]])
        # print(x,y)
        if x in g[y]:
            xor.append(y)
        elif y in g[x]:
            xor.append(x)
    print(' '.join(map(str, xor)))


func()

n = int(input())
a = [list(map(lambda x: x - 1, map(int, input().split()))) for i in range(n)]
start = 0
flag = False
ans = []
should_be = -1
while True:
  if start == 0 and flag == True:
    break
  ans.append(start + 1)
  flag = True
  next = a[start][0]
  ok = should_be == -1 or should_be == next
  if ok and (a[start][1] == a[next][0] or a[start][1] == a[next][1]):
    if should_be > -1:
      assert next == should_be
    should_be = a[start][1]
    start = next
    continue
  next = a[start][1]
  ok = should_be == -1 or should_be == next
  if ok and (a[start][0] == a[next][0] or a[start][0] == a[next][1]):
    if should_be > -1:
      assert next == should_be
    should_be = a[start][0]
    start = next
    continue
  assert False
for x in ans:
  print(x, end=' ')


def read(type = 1):
    if type:
        file = open("input.dat", "r")
        n = int(file.readline())
        a = []
        for i in range(n):
            a.append(list(map(int, file.readline().split())))
        file.close()
    else:
        n = int(input().strip())
        a = []
        for i in range(n):
            a.append(list(map(int, input().strip().split())))
    return n, a


def solve():
    sol = [1]
    used = [0 for i in range(n)]
    while len(sol) < n - 1:
        last = sol[-1] - 1
        used[last] = 1
        if a[last][0] in a[a[last][1]-1]:
            sol.append(a[last][1])
            used[a[last][1]-1] = 1
            sol.append(a[last][0])
        else:
            sol.append(a[last][0])
            used[a[last][0] - 1] = 1
            sol.append(a[last][1])
    used[sol[-1] - 1] = 1
    if len(sol) != n:
        for i in range(n):
            if used[i] == 0:
                sol.append(i+1)
    return sol


def write(sol):
    line = ""
    for v in sol:
        line += str(v) + " "
    print(line)


n, a = read(0)
sol = solve()
write(sol)

n = int(input())

arr = [-1]

a = [[]]
for i in range(n):
    a.append(list(map(int,input().split())))

arr.append(1)
if a[1][0] not in a[a[1][1]]:
    arr.append(a[1][0])
    arr.append(a[1][1])
else:
    arr.append(a[1][1])
    arr.append(a[1][0])
while(len(arr) < n+1):
    if a[arr[-2]][0]  != arr[-1]:
        arr.append(a[arr[-2]][0])
    else:
        arr.append(a[arr[-2]][1])

for i in range(1,len(arr)-1):
    print(arr[i],end=" ")
print(arr[n])

n = int(input())

arr = [-1]

a = [[]]
for i in range(n):
    a.append(list(map(int,input().split())))

arr.append(1)
if a[1][0] not in a[a[1][1]]:
    arr.append(a[1][0])
    arr.append(a[1][1])
else:
    arr.append(a[1][1])
    arr.append(a[1][0])
while(len(arr) < n+1):
    if a[arr[-2]][0]  != arr[-1]:
        arr.append(a[arr[-2]][0])
    else:
        arr.append(a[arr[-2]][1])

for i in range(1,len(arr)-1):
    print(arr[i],end=" ")
print(arr[n])

#15:35

n = int(input())
circ = []
l = []

for i in range(n):
    a1, a2 = map(int, input().split())
    a1 -= 1
    a2 -= 1

    l.append((a1, a2))

circ.append(l[0][0])
circ.append(l[0][1])

for i in range(0, n - 1):
    p = l[circ[i]]
    
    if circ[i + 1] not in p:
        circ[i], circ[i + 1] = circ[i + 1], circ[i]

    p = l[circ[i]]

    if circ[i + 1] == p[0]:
        circ.append(p[1])

    else:
        circ.append(p[0])

for i in range(n):
    print(circ[i] + 1, end = ' ')