Bob is an avid fan of the video game "League of Leesins", and today he celebrates as the League of Leesins World Championship comes to an end! 

The tournament consisted of $n$ ($n \ge 5$) teams around the world. Before the tournament starts, Bob has made a prediction of the rankings of each team, from $1$-st to $n$-th. After the final, he compared the prediction with the actual result and found out that the $i$-th team according to his prediction ended up at the $p_i$-th position ($1 \le p_i \le n$, all $p_i$ are unique). In other words, $p$ is a permutation of $1, 2, \dots, n$.

As Bob's favorite League player is the famous "3ga", he decided to write down every $3$ consecutive elements of the permutation $p$. Formally, Bob created an array $q$ of $n-2$ triples, where $q_i = (p_i, p_{i+1}, p_{i+2})$ for each $1 \le i \le n-2$. Bob was very proud of his array, so he showed it to his friend Alice.

After learning of Bob's array, Alice declared that she could retrieve the permutation $p$ even if Bob rearranges the elements of $q$ and the elements within each triple. Of course, Bob did not believe in such magic, so he did just the same as above to see Alice's respond.

For example, if $n = 5$ and $p = [1, 4, 2, 3, 5]$, then the original array $q$ will be $[(1, 4, 2), (4, 2, 3), (2, 3, 5)]$. Bob can then rearrange the numbers within each triple and the positions of the triples to get $[(4, 3, 2), (2, 3, 5), (4, 1, 2)]$. Note that $[(1, 4, 2), (4, 2, 2), (3, 3, 5)]$ is not a valid rearrangement of $q$, as Bob is not allowed to swap numbers belong to different triples.

As Alice's friend, you know for sure that Alice was just trying to show off, so you decided to save her some face by giving her any permutation $p$ that is consistent with the array $q$ she was given. 


-----Input-----

The first line contains a single integer $n$ ($5 \le n \le 10^5$) — the size of permutation $p$.

The $i$-th of the next $n-2$ lines contains $3$ integers $q_{i, 1}$, $q_{i, 2}$, $q_{i, 3}$ ($1 \le q_{i, j} \le n$) — the elements of the $i$-th triple of the rearranged (shuffled) array $q_i$, in random order. Remember, that the numbers within each triple can be rearranged and also the positions of the triples can be rearranged.

It is guaranteed that there is at least one permutation $p$ that is consistent with the input. 


-----Output-----

Print $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) such that $p$ is consistent with array $q$. 

If there are multiple answers, print any. 


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

Output
1 4 2 3 5

Difficulty: interview

Starter code:

Solutions:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i*i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD

def flush():
    return sys.stdout.flush()

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
n = int(input())
a = [arrIN() for _ in range(n-2)]
d = [0]*(n+1)
pos = defaultdict(list)
for i in range(n-2):
    for j in a[i]:
        d[j]+=1
        pos[j].append(i)
ans = []
flag = [1]*(n-2)
for i in range(1,n+1):
    if d[i]==1:
        x  = a[pos[i][0]]
        flag[pos[i][0]] = 0
        break
t = [0,0,0]
for i in x:
    if d[i]==1:
        t[0] = i
    elif d[i]==2: 
        t[1] = i
    else:
        t[2] = i
ans = t
l = 3
while l!=n:
    for i in pos[ans[-2]]:
        if flag[i]:
            if ans[-1] in a[i]:
                x = a[i]
                flag[i] = 0
                break

    t = [i for i in x]
    t.remove(ans[-2])
    t.remove(ans[-1])
    ans.append(t[0])
    l+=1
print(*ans)

from collections import defaultdict

n = int(input())

nei = defaultdict(list)

q = []
for i in range(n-2):
	a, b, c = map(lambda x: int(x)-1, input().split())
	q.append((a, b, c))
	nei[tuple(sorted((a, b)))].append(c)
	nei[tuple(sorted((a, c)))].append(b)
	nei[tuple(sorted((b, c)))].append(a)

counts = [0] * n
for a,b,c in q:
	counts[a] += 1
	counts[b] += 1
	counts[c] += 1

start = next(filter(lambda i: counts[i]==1, range(n)))
for abc in q:
	if start in abc:
		break

a, b, c = abc

if b==start:
	a, b = b, a
elif c==start:
	a, c = c, a

if counts[b] != 2:
	b, c = c, b

p = [a, b, c]

while len(p) < n:
	candidates = nei[tuple(sorted((p[-2], p[-1])))]
	ne = candidates[0]
	if candidates[0] == p[-3]:
		ne = candidates[1]
	p.append(ne)

print(*[x+1 for x in p])

n = int(input())
mas = []
cou = []
for i in range(n + 1):
	mas.append([])
	cou.append(0)
for i in range(n - 2):
	a, b, c = list(map(int, input().split()))
	mas[a].append([a, b, c])
	mas[b].append([a, b, c])
	mas[c].append([a, b, c])
	cou[a] += 1
	cou[b] += 1
	cou[c] += 1
for i in range(1, n + 1):
	if cou[i] == 1:
		x = i
		break
y = -1
for i in range(1, n + 1):
	if cou[i] == 2:
		if y == -1:
			y = i
		else:
			z = i
if not(y in mas[x][0]):
	y = z
for i in mas[x][0]:
	if i != x and i != y:
		z = i
		break
ans = [x, y, z]
for k in range(3, n):
	x = ans[k - 3]
	y = ans[k - 2]
	z = ans[k - 1]
	for i in mas[y]:
		if y in i and z in i and not(x in i):
			for j in range(len(i)):
				if i[j] != y and i[j] != z:
					h = i[j]
					break
	ans.append(h)
print(*ans)












from collections import defaultdict

n = int(input())

A = []

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

count = {i + 1: 0 for i in range(n)}
third = {}

for a, b, c in A:
	if (a, b) not in third:
		third[(a, b)] = []
	third[(a, b)].append(c)
		
	if (b, a) not in third:
		third[(b, a)] = []
	third[(b, a)].append(c)
		
	if (a, c) not in third:
		third[(a, c)] = []
	third[(a, c)].append(b)
		
	if (c, a) not in third:
		third[(c, a)] = []
	third[(c, a)].append(b)
		
	if (b, c) not in third:
		third[(b, c)] = []
	third[(b, c)].append(a)
		
	if (c, b) not in third:
		third[(c, b)] = []
	third[(c, b)].append(a)
		

	count[a] += 1
	count[b] += 1
	count[c] += 1

first = 0

for i in range(n):
	if count[i + 1] == 1:
		first = i + 1
		break

second = 0
for i in range(n):
	if count[i + 1] == 2:
		second = i + 1

		if (first, second) in third:
			break
		else:
			second = 0

ans = [first, second]
aset = set()
aset.add(first)
aset.add(second)

for i in range(n - 2):
	for val in third[(first, second)]:
		if val not in aset:
			ans.append(val)
			aset.add(val)

			first, second = second, val

			break

print(*ans)

n=int(input())
d={}
used=set()
for itr in range(n-2):
    p,q,r=map(int,input().split())
    if p in d: d[p].append([p,q,r])
    else: d[p]=[[p,q,r]]
    if q in d: d[q].append([p,q,r])
    else: d[q]=[[p,q,r]]
    if r in d: d[r].append([p,q,r])
    else: d[r]=[[p,q,r]]
ans=[]
for itr in d:
    if len(d[itr])==1: 
        k=itr
        break
ans.append(k)
used.add(frozenset(d[k][0]))
for itr in d[k][0]:
    if itr==k: continue
    ans.insert(len(d[itr])-1,itr)
for itr in range(1,n-2):
    for tup in d[ans[itr]]:
        if frozenset(tup) in used: continue
        for i in tup:
            if i==ans[itr] or i==ans[itr+1]: continue
            ans.append(i)
        used.add(frozenset(tup))
print(*ans)

import sys
from collections import defaultdict
n = int(input())
count = [0]*(n+1)
d = defaultdict(list)
di = 10**6

for q1, q2, q3 in (list(map(int, l.split())) for l in sys.stdin):
    count[q1] += 1
    count[q2] += 1
    count[q3] += 1
    d[q1*di + q2 if q1 < q2 else q2*di + q1].append(q3)
    d[q1*di + q3 if q1 < q3 else q3*di + q1].append(q2)
    d[q2*di + q3 if q2 < q3 else q3*di + q2].append(q1)


i1, i2 = [], []
for i in range(1, n+1):
    if count[i] == 1:
        i1.append(i)
    elif count[i] == 2:
        i2.append(i)

key = []
ans = [0]*n
if (i1[0]*di + i2[0] if i1[0] < i2[0] else i2[0]*di + i1[0]) in d:
    key = [i1[0], i2[0]]
else:
    key = [i1[0], i2[1]]

ans[0], ans[1] = key[0], key[1]
used = {key[0], key[1]}

for i in range(2, n):
    next_key = key[0]*di + key[1] if key[0] < key[1] else key[1]*di + key[0]
    next_l = d[next_key]
    next_n = next_l[0] if next_l[0] not in used else next_l[1]
    #print(key, next_key, next_n)
    ans[i] = next_n
    key[0], key[1] = key[1], next_n
    used.add(next_n)

print(*ans)


import sys
input = sys.stdin.readline

n = int(input())
adj_list = [[] for _ in range(n)]

for _ in range(n-2):
    q1, q2, q3 = map(int, input().split())
    adj_list[q1-1].append(q2-1)
    adj_list[q1-1].append(q3-1)
    adj_list[q2-1].append(q3-1)
    adj_list[q2-1].append(q1-1)
    adj_list[q3-1].append(q1-1)
    adj_list[q3-1].append(q2-1)

for i in range(n):
    adj_list[i] = list(set(adj_list[i]))
    
for i in range(n):
    if len(adj_list[i])==2:
        start = i
        break

ans = [start]
n1 = adj_list[start][0]
n2 = adj_list[start][1]

if len(adj_list[n1])==3:
    ans.append(n1)
else:
    ans.append(n2)

for i in range(2, n):
    n1 = ans[i-2]
    n2 = ans[i-1]
    s1 = set(adj_list[n1])
    s2 = set(adj_list[n2])
    s3 = s1&s2
    #print(i, n1, n2)
    if i>=3:
        s3.remove(ans[i-3])
    
    #print(n1, adj_list[n1], n2, adj_list[n2], s3)
    ans.append(list(s3)[0])
    #print(ans)
ans2 = [ai+1 for ai in ans]

print(*ans2)


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(k=0): return [int(x)+k for x in sys.stdin.readline().split()]
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()

aa = [inpl(-1) for _ in range(N-2)]
cnts = [set() for _ in range(N)]
for i,(a1,a2,a3) in enumerate(aa):
    cnts[a1].add(i)
    cnts[a3].add(i)
    cnts[a2].add(i)

first = True
c2 = []
for c,s in enumerate(cnts):
    if len(s) == 1:
        if first:
            ai = list(s)[0]
            pp = [c]
            first = False
        else:
            last_ai = list(s)[0]
            last_p = c
    elif len(s) == 2:
        c2.append(c)


cnts[last_p].add(-1)
cnts[last_p].add(-2)

for c in c2:
    if last_ai in cnts[c]:
        cnts[c].add(-1)
        last_2p = c


# print(cnts)

for _ in range(N-3):
    for ci in aa[ai]:
        cnts[ci].remove(ai)
        if len(cnts[ci]) == 1:
            next_ai = list(cnts[ci])[0]
            pp.append(ci)
    ai = next_ai
    # print(cnts,next_ai)

pp += [last_2p, last_p]

print(' '.join([str(p+1) for p in pp]))


def common(l1,l2):
	for i in range(3):
		for j in range(3):
			if l1[i]==l2[j]:
				return l1[i]
	return 0

def comp(l1,a,b):
	for i in l1:
		if i!=a and i!=b:
			return i

n=int(input())
l=[]
d={}
commons = {}
for i in range(n-2):
	l.append(list(map(int,input().split())))
for i in range(n-2):
	for j in l[i]:
		if j in d:
			d[j].append(i)
		else:
			d[j]=[i]
start = -1
end = -1
for i in d:
	if len(d[i])==1:
		if start==-1:
			start = i
			startg = d[i][0]
		else:
			end = i
			endg = d[i][0]
			break
#print (d)
for i in l[startg]:
	if len(d[i])==2:
		second = i
		break
for i in l[endg]:
	if len(d[i])==2:
		seclast = i
		break
i=1
ans = [-1]*n
ans[0]=start
ans[1]=second
ans[n-1]=end
ans[n-2]=seclast
if ans[i-1] in l[d[ans[i]][0]]:
	ans[i+1]=comp(l[d[ans[i]][0]],ans[i-1],ans[i])
elif ans[i-1] in l[d[ans[i]][1]]:
	ans[i+1]=comp(l[d[ans[i]][1]],ans[i-1],ans[i])
else:
	ans[i+1]=comp(l[d[ans[i]][2]],ans[i-1],ans[i])
i+=1
#print (ans)
while i<n-3:
	#print (i,ans[i],d[ans[i]])
	if ans[i-1] in l[d[ans[i]][0]] and ans[i-2] not in l[d[ans[i]][0]]:
		ans[i+1]=comp(l[d[ans[i]][0]],ans[i-1],ans[i])
	elif ans[i-1] in l[d[ans[i]][1]] and ans[i-2] not in l[d[ans[i]][1]]:
		ans[i+1]=comp(l[d[ans[i]][1]],ans[i-1],ans[i])
	else:
		ans[i+1]=comp(l[d[ans[i]][2]],ans[i-1],ans[i])
	i+=1
print(*ans)


import sys
input=sys.stdin.readline
from collections import defaultdict as dd
n=int(input())
l=[]
cc=[0]*(n+1)
d=dd(list)
res=[]
one=[]
two=[]
for i in range(n-2):
    a,b,c=map(int,input().split())
    l.append((a,b,c))
    cc[a]+=1
    cc[b]+=1
    cc[c]+=1
    d[a].append((a,b,c))
    d[b].append((a,b,c))
    d[c].append((a,b,c))
for i in range(len(cc)):
    if(cc[i]==1):
        one.append(i)
    if(cc[i]==2):
        two.append(i)
f=d[one[0]]
#print(one)
prev=[one[0]]
if(cc[f[0][0]]==2):
    prev.append(f[0][0])
if(cc[f[0][1]]==2):
    prev.append(f[0][1])
if(cc[f[0][2]]==2):
    prev.append(f[0][2])
if(cc[f[0][0]]==3):
    prev.append(f[0][0])
if(cc[f[0][1]]==3):
    prev.append(f[0][1])
if(cc[f[0][2]]==3):
    prev.append(f[0][2])
res.append(prev)
cur=[]
k=n-3
#print(cc)
while k:
    for j in d[prev[1]]:
        if(prev[2] in j and prev[0] not in j):
            f=j
            break
    prev=[prev[1],prev[2]]
    for v in j:
        if(v!=prev[0] and v!=prev[1]):
            prev.append(v)
    res.append(prev)
    k-=1
#print(res)
print(res[0][0],res[0][1],res[0][2],end=" ")
for i in range(1,len(res)):
    print(res[i][2],end=" ")


from collections import defaultdict as dd
n=int(input())
l=[]
d=dd(list)
d2=dd(list)
for _ in range(n-2):
    a,b,c=list(map(int,input().split()))
    l+=[[a,b,c]]
    
for i in range(n-2):
    d[l[i][0]]+=[i]
    d[l[i][1]]+=[i]
    d[l[i][2]]+=[i]
for i in range(n-2):
    d2[(l[i][0],l[i][1])]+=[l[i][2]]
    d2[(l[i][1],l[i][2])]+=[l[i][0]]
    d2[(l[i][2],l[i][1])]+=[l[i][0]]
    d2[(l[i][1],l[i][0])]+=[l[i][2]]
    d2[(l[i][0],l[i][2])]+=[l[i][1]]
    d2[(l[i][2],l[i][0])]+=[l[i][1]]
for i in d:
    if(len(d[i])==1):
        k=i
        break
ans=[k]
bef=k
#print(d,k)
for i in d:
    if (len(d[i])==2):
        for j in d[i]:
            if j==d[k][0]:
               
                p=i
                break

ans+=[p]
ind=d[k][0]
#print(ans)
'''
for i in d[tuple(ans)]:
    if i not in ans:
        ans+=[i]
        nex+=[i]
        break
'''
nex=[ans[0],ans[1]]
#print(ans)
bef=99999999999999
for i in range(n-2):
    for j in d2[tuple(nex)]:
        if j !=bef:
            ans+=[j]
    bef=nex.pop(0)
    nex+=[ans[-1]]
print(*ans)
    
    
    


n = int(input())
ar = []
for i in range(n-2):
    ar.append(list(map(int,input().split())))
#print(ar)

br = [False]*n
vr = [0]*n
rel = dict()
ans = []

for i in range(n):
    rel[i+1] = set()

for i in range(n-2):
    a = ar[i][0]
    b = ar[i][1]
    c = ar[i][2]

    rel[a].add(b)
    rel[a].add(c)
    rel[b].add(a)
    rel[b].add(c)
    rel[c].add(a)
    rel[c].add(b)

#print(rel)

for i in range(n):
    if len(rel[i+1])==2:
        start = i+1
        break

#print(start)

br[start-1] = True
ans.append(start)
for i in rel[start]:
    if len(rel[i])==3:
        ans.append(i)
        br[i-1] = True
    else:
        x = i
ans.append(x)
br[x-1] = True
#print(ans,br,x)

i = 1
while(i<n-2):
    for j in rel[ans[i]]:
        if br[j-1]==False:
            ans.append(j)
            br[j-1] = True
            break
    #print(br,ans,i)
    i+=1

for i in range(n):
    print(ans[i],end =" ")
print()


n=int(input())
h={}
for i in range(n-2):
    x,y,z=map(int,input().split())
    if x not in h:
        h[x]=[]
    if y not in h:
        h[y]=[]
    if z not in h:
        h[z]=[]
    h[x].append(y)
    h[x].append(z)
    h[x]=set(h[x])
    h[x]=list(h[x])
    h[y].append(x)
    h[y].append(z)
    h[y]=set(h[y])
    h[y]=list(h[y])
    h[z].append(x)
    h[z].append(y)
    h[z]=set(h[z])
    h[z]=list(h[z])

single=0
for i in h:
    if len(h[i])==2:
        single=i
        break
ans=[]
vis={}
vis[single]=True
ans.append(single)
first=single

if len(h[ h[single][0] ])==3:
    ans.append(h[single][0])
    vis[h[single][0]]=True
    second=h[single][0]
else:
    ans.append(h[single][1])
    vis[h[single][1]]=True
    second=h[single][1]
for i in range(n-2):
    a=h[first]
    b=h[second]
    a=set(a)
    b=set(b)
    a=a.intersection(b)
    a=list(a)
    for x in a:
        if x not in vis:
            ans.append(x)
            vis[x]=True
            first=second
            second=x
            break
print(" ".join(map(str,ans)))

n = int(input())
n1 = n - 2
d = {}
d1 = {}
visit = {}
l1 = []
for i in range(1, n + 1):
	d[i] = []
	d1[i] = 0
	visit[i] = False
while n1:
	n1 -= 1
	a, b, c = list(map(int, input().split()))
	d[a].append(b)
	d[a].append(c)
	d1[a] += 1
	d[b].append(a)
	d[b].append(c)
	d1[b] += 1
	d[c].append(b)
	d[c].append(a)
	d1[c] += 1
d1 = dict(sorted(list(d1.items()), key = lambda x : x[1]))
for i in d1:
	#print(i)
	if not visit[i]:
		visit[i] = True
		l1.append(i)
	x = sorted(d[i], key = lambda x : d1[x])
	for j in x:
		if not visit[j]:
			visit[j] = True
			l1.append(j)
			x += d[j]
	#print(l1)
print(*l1)


n=int(input())
arr=[]
d={}
for i in range(n-2):
    a,b,c=map(int,input().split())
    arr.append([a,b,c])
    d[a]=d.get(a,[]) + [i]
    d[b]=d.get(b,[]) + [i]
    d[c]=d.get(c,[]) + [i]
# print(d)    
for i in d:
    if len(d[i])==1:
        ind=d[i][0]
        
vis=[0]*(n-2)
visno=[0]*(n+1)
q=[arr[ind]]
vis[ind]=1
# print(d)
# print(arr)
if len(d[q[0][0]])==1:
    print(q[0][0],end=" ")
    visno[q[0][0]]=1
                
    
elif len(d[q[0][1]])==1:
    print(q[0][1],end=" ")
    visno[q[0][1]]=1
    
else:
    print(q[0][2],end=" ")
    visno[q[0][2]]=1
    
# print(q)

if len(d[q[0][0]])==2:
    print(q[0][0],end=" ")
    visno[q[0][0]]=1
    prev=q[0][0]
    if len(d[q[0][0]])==2:
        for i in (d[q[0][0]]):
            if vis[i]==0:
                q.append(arr[i])
                vis[i]=1
                
    
elif len(d[q[0][1]])==2:
    print(q[0][1],end=" ")
    visno[q[0][1]]=1
    prev=q[0][1]
    if len(d[q[0][1]])==2:
        for i in (d[q[0][1]]):
            if vis[i]==0:
                q.append(arr[i])
                vis[i]=1
    
else:
    print(q[0][2],end=" ")
    visno[q[0][2]]=1
    prev=q[0][2]
    if len(d[q[0][2]])==2:
        for i in (d[q[0][2]]):
            if vis[i]==0:
                q.append(arr[i])
                vis[i]=1
# q.pop(0)
# print(q)
for i in range(n-4):
    p=q.pop(0)
    for j in p:
        if visno[j]==0:
            visno[j]=1
            for k in d[j]:
                if vis[k]==0:
                    vis[k]=1
                    q.append(arr[k])
                    print(j,end=" ")
                    break
            break
q.pop(0)
# print(q)        
for j in q[0]:
    if len(d[j])==2:
        print(j,end=" ")
        
for j in q[0]:
    if len(d[j])==1:
        print(j,end=" ")
        
# for i in range()        


def solve(a,b,groups,nums,visited):
    group1 = set(nums[a])
    group2 = set(nums[b])
    common = group1&group2
    for i in common:
        if i not in visited:
            group = i

    #print(group)
    visited.add(group)
    for i in groups[group]:
        if i != a and i != b:
            return i
    

def main():
    n = int(input())
    nums = {}
    ans = []
    groups = []
    for i in range(n-2):
        arr = list(map(int,input().split()))
        for j in arr:
            if j not in nums.keys():
                nums[j] = [i]
            else:
                nums[j].append(i)

        groups.append(arr)

    first = -1
    for i in nums.keys():
        if len(nums[i]) == 1:
            first = i
            break

    visited = set()
    ans.append(first)
    group = nums[first][0]
    for i in groups[group]:
        if len(nums[i]) == 2:
            second = i
            break
        
    ans.append(second)
    for i in groups[group]:
        if i not in ans:
            ans.append(i)
            break

    visited.add(group)
    a = ans[-2]
    b = ans[-1]
    for i in range(n-3):
        ans.append(solve(a,b,groups,nums,visited))
        a = ans[-2]
        b = ans[-1]

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

main()


#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
triple = []
indexes = [[] for _ in range(n)]
cnt = [0] * n
abc = []
for i in range(n-2):
    a, b, c = [int(item)-1 for item in input().split()]
    abc.append((a, b, c))
    indexes[a].append(i)
    indexes[b].append(i)
    indexes[c].append(i)
    cnt[a] += 1
    cnt[b] += 1
    cnt[c] += 1
tmp = cnt[:]

ans = []
node = cnt.index(1)
visited = [0] * (n - 2)
nxt = indexes[node][0]
while True:
    for item in indexes[node]:
        if visited[item]:
            continue
        nxt = item
        visited[nxt] = 1
    a, b, c = abc[nxt]
    if cnt[a] == 1 and cnt[b] == 1 and cnt[c] == 1:
        break
    ans.append(node+1)
    cnt[a] -= 1
    cnt[b] -= 1
    cnt[c] -= 1
    if cnt[a] == 1:
        node = a
    elif cnt[b] == 1:
        node = b
    elif cnt[c] == 1:
        node = c

for item in abc[nxt]:
    if tmp[item] == 3:
        ans.append(item + 1)
for item in abc[nxt]:
    if tmp[item] == 2:
        ans.append(item + 1)
for item in abc[nxt]:
    if tmp[item] == 1:
        ans.append(item + 1)

print(" ".join([str(item) for item in ans]))

a = int(input())
A = []
for i in range(a):
    A.append(set())
for i in range(a - 2):
    x, y, z = list(map(int, input().split()))
    x -= 1
    y -= 1
    z -= 1
    A[x].add(y)
    A[x].add(z)
    A[y].add(x)
    A[y].add(z)
    A[z].add(x)
    A[z].add(y)
for i in range(len(A)):
    if len(A[i]) == 2:
        k = i
m2 = k
B = [k + 1]
Z = list(A[k])
if len(A[Z[0]]) == 3:
    B.append(Z[0] + 1)
    m1 = Z[0]
else:
    B.append(Z[1] + 1)
    m1 = Z[1]
for i in range(a - 2):
    w = list(A[m1] & A[m2])
    if len(B) > 2:
        if w[0] + 1 != B[-3]:
            B.append(w[0] + 1)
            m2 = int(m1)
            m1 = w[0]

        else:
            B.append(w[1] + 1)
            m2 = int(m1)
            m1 = w[1]
    else:
        B.append(w[0] + 1)
        m2 = int(m1)
        m1 = w[0]


print(*B)



from collections import defaultdict

n = int(input())
# q = []
# d = defaultdict(int)
# for i in range(n-2):
#     a = list(map(int,input().split()))
#     d[a[0]] += 1
#     d[a[1]] += 1
#     d[a[2]] += 1
#     q.append(a)
#
# a = list(d.items())
# a.sort(key=lambda x: x[1])
#

graph = [[] for i in range(n+1)]

for _ in range(n-2):
    a = list(map(int, input().split()))
    graph[a[0]] += [a[1], a[2]]
    graph[a[1]] += [a[0], a[2]]
    graph[a[2]] += [a[1], a[0]]

for i in range(1, n+1):
    graph[i] = list(set(graph[i]))

visited = [False for i in range(n+1)]

ans = []

for i in range(1,n+1):
    if len(graph[i]) == 2:
        ans.append(i)
        visited[i] = True
        break
# print(ans)
for j in graph[i]:
    if len(graph[j]) == 3:
        ans.append(j)
        visited[j] = True
        break
# print(ans)
for i in range(n-2):
    for j in graph[ans[i]]:
        if not visited[j]:
            ans.append(j)
            visited[j] = True
            # print(ans)

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

n = int(input())
q = []
qh = {}
qc = {}
for i in range(n):
    qh[i] = []
    qc[i] = 0
for i in range(n-2):
    q1, q2, q3 = list(map(int, input().split()))
    q.append([q1-1, q2-1, q3-1])
    for d in [q1, q2, q3]:
        qh[d-1].append(i)
        qc[d-1] += 1
pp = []
for i in range(n):
    if qc[i] == 1:
        pp.append(i)
p1, p2 = pp
p3 = -1
p4 = -1
for i in q[qh[p2][0]]:
    if qc[i] == 3:
        p3 = i
    if qc[i] == 2:
        p4 = i
p5, p6 = -1, -1
for i in q[qh[p1][0]]:
    if qc[i] == 3:
        p5 = i
    if qc[i] == 2:
        p6 = i
    qc[i] -= 1
p = [p1, p6, p5]
d = qh[p6][0]
if d == qh[p1][0]:
    d = qh[p6][1]
for i in q[d]:
    qc[i] -= 1
for i in range(n-6):
    fg = p[-1]
    d = -1
    for j in qh[fg]:
        if j not in qh[p[-2]]:
            d = j
    for j in q[d]:
        if qc[j] == 2:
            p.append(j)
        qc[j] -= 1
if n != 5:
    p.append(p3)
p.append(p4)
p.append(p2)
print(' '.join([str(x+1) for x in p]))





rinp = [4,6,2,1,7,3,5]


'''
7
4 6 2
6 2 1
2 1 7
1 7 3
7 3 5
'''


n = int(input())

ans = list()

BIN = list((i, list()) for i in range(n))

i = 2
while i < n:
  inp = list(int(x)-1 for x in input().split())
  for ch in inp:
    BIN[ch][1].append(inp)

  i += 1

SB = sorted(BIN, key=lambda x:len(x[1]))
#[print(x) for x in (BIN)]
#print()
#[print(x) for x in (SB)]

now = SB[0][0]
last = None
while True:
  ans.append(now)
  nowl = BIN[now][1]
  #print(f"{now}={last}={nowl}=========={ans}")
  lnowl = len(nowl)
  if lnowl == 3:#mid
    for item in nowl:
      try:item.remove(now)
      except:pass
      try:item.remove(last)
      except:pass
      if len(item) == 1:
        next = item[0]
        break
  elif lnowl == 2:
    for item in nowl:
      try:item.remove(now)
      except:pass
      try:item.remove(last)
      except:pass
      if len(item) == 1:
        next = item[0]
        break
  else:#first last
    tl = nowl[0]
    tl.remove(now)
    if not tl:
      break
    for next in tl:
      ttl = BIN[next][1]
      if len(ttl) == 2:
        break
  now, last = next, now


print(" ".join(str(x + 1) for x in ans))


#!/usr/bin/env python3
import sys

#lines = stdin.readlines()
def rint():
    return list(map(int, sys.stdin.readline().split()))

def input():
    return sys.stdin.readline().rstrip('\n')

def oint():
    return int(input())


n = oint()
a = []
m = dict()
for i in range(n-2):
    q = list(rint())
    a.append(q)
    for j in range(3):
        if q[j] in m:
            m[q[j]] = m[q[j]] + [i]

        else:
            m[q[j]] = [i]
start = []
second = []
for j in range(1, n+1):
    if len(m[j]) == 1:
        start.append(j)
    if len(m[j]) == 2:
        second.append(j)
s = start[0]
if m[s][0] in m[second[0]]:
    sec = second[0]
else:
    sec = second[1]
ans = [s, sec]
for i in range(2, n):
    qi = set(m[ans[i-2]]).intersection(set(m[ans[i-1]]))
    if len(qi) == 1:
        next = set(a[qi.pop()]).difference(set([ans[i-2], ans[i-1]])).pop()
    else:
        next1 = set(a[qi.pop()]).difference(set([ans[i-2], ans[i-1]])).pop()
        next2 = set(a[qi.pop()]).difference(set([ans[i-2], ans[i-1]])).pop()
        if next1 == ans[-3]:
            next = next2
        else:
            next = next1
    ans.append(next)



print(*ans)




n = int(input().strip())

g = {}
rg = {}
cnt = {}


for i in range(1, n + 1):
    cnt[str(i)] = 0
    rg[str(i)] = []

for _ in range(n - 2):
    arr = [x for x in input().split()]
    arr.sort()
    a, b, c = arr
    for e in arr:
        cnt[e] += 1
    
    for p, tr in [((a, b), c), ((a, c), b), ((b, c), a)]:
        if p not in g:
            g[p] = []
        rg[tr].append(p)
        g[p].append(tr)
    

cur = None
for k in cnt:
    if cnt[k] == 1:
        cur = k

was = set()
was.add(cur)
res = [cur, ]

ca, cb = rg[cur][0]

if cnt[ca] == 2:
    cur = ca
else:
    cur = cb

was.add(cur)
res.append(cur)

while len(res) != n:
    cur = [res[-1], res[-2]]
    cur.sort()
    cur = tuple(cur)
    for to in g[cur]:
        if to in was:
            continue
        res.append(to)
        was.add(to)

print(' '.join(res))