We are committed to the well being of all participants. Therefore, instead of the problem, we suggest you enjoy a piece of cake.

Uh oh. Somebody cut the cake. We told them to wait for you, but they did it anyway. There is still some left, though, if you hurry back. Of course, before you taste the cake, you thought about how the cake was cut.

It is known that the cake was originally a regular $n$-sided polygon, each vertex of which had a unique number from $1$ to $n$. The vertices were numbered in random order.

Each piece of the cake is a triangle. The cake was cut into $n - 2$ pieces as follows: each time one cut was made with a knife (from one vertex to another) such that exactly one triangular piece was separated from the current cake, and the rest continued to be a convex polygon. In other words, each time three consecutive vertices of the polygon were selected and the corresponding triangle was cut off.

A possible process of cutting the cake is presented in the picture below. [Image] Example of 6-sided cake slicing. 

You are given a set of $n-2$ triangular pieces in random order. The vertices of each piece are given in random order — clockwise or counterclockwise. Each piece is defined by three numbers — the numbers of the corresponding $n$-sided cake vertices.

For example, for the situation in the picture above, you could be given a set of pieces: $[3, 6, 5], [5, 2, 4], [5, 4, 6], [6, 3, 1]$.

You are interested in two questions.  What was the enumeration of the $n$-sided cake vertices?  In what order were the pieces cut? 

Formally, you have to find two permutations $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) and $q_1, q_2, \dots, q_{n - 2}$ ($1 \le q_i \le n - 2$) such that if the cake vertices are numbered with the numbers $p_1, p_2, \dots, p_n$ in order clockwise or counterclockwise, then when cutting pieces of the cake in the order $q_1, q_2, \dots, q_{n - 2}$ always cuts off a triangular piece so that the remaining part forms one convex polygon.

For example, in the picture above the answer permutations could be: $p=[2, 4, 6, 1, 3, 5]$ (or any of its cyclic shifts, or its reversal and after that any cyclic shift) and $q=[2, 4, 1, 3]$.

Write a program that, based on the given triangular pieces, finds any suitable permutations $p$ and $q$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then there are $t$ independent sets of input data.

The first line of each set consists of a single integer $n$ ($3 \le n \le 10^5$) — the number of vertices in the cake.

The following $n - 2$ lines describe the numbers of the pieces vertices: each line consists of three different integers $a, b, c$ ($1 \le a, b, c \le n$) — the numbers of the pieces vertices of cake given in random order. The pieces are given in random order.

It is guaranteed that the answer to each of the tests exists. It is also guaranteed that the sum of $n$ for all test cases does not exceed $10^5$.


-----Output-----

Print $2t$ lines — answers to given $t$ test cases in the order in which they are written in the input. Each answer should consist of $2$ lines.

In the first line of an answer on a test case print $n$ distinct numbers $p_1, p_2, \dots, p_n$($1 \le p_i \le n$) — the numbers of the cake vertices in clockwise or counterclockwise order.

In the second line of an answer on a test case print $n - 2$ distinct numbers $q_1, q_2, \dots, q_{n - 2}$($1 \le q_i \le n - 2$) — the order of cutting pieces of the cake. The number of a piece of the cake corresponds to its number in the input.

If there are several answers, print any. It is guaranteed that the answer to each of the tests exists.


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

Output
1 6 4 2 5 3 
4 2 3 1 
1 4 2 6 5 3 
3 4 2 1 
1 3 2 
1

Difficulty: VERY_HARD
Tags: Graph algorithms

Data structures

Graph traversal

Constructive algorithms
Skill types: Data structures

Starter code:

Solutions:
import os
from io import BytesIO
import sys
import threading
sys.setrecursionlimit(10 ** 9)
threading.stack_size(67108864)

def main():

	def ad(i, j):
		nonlocal g
		if j in g[i]:
			g[i].remove(j)
			g[j].remove(i)
		else:
			g[i].add(j)
			g[j].add(i)

	def dfs(v):
		nonlocal used, g, nans
		used[v] = True
		nans.append(v + 1)
		for el in g[v]:
			if not used[el]:
				dfs(el)
	for _ in range(int(input())):
		n = int(input())
		cnt = [set() for i in range(n)]
		g = [set() for i in range(n)]
		used = [False] * n
		triangles = []
		for i in range(n - 2):
			(a, b, c) = map(int, input().split())
			a -= 1
			b -= 1
			c -= 1
			cnt[a].add(i)
			cnt[b].add(i)
			cnt[c].add(i)
			triangles.append((a, b, c))
			ad(a, b)
			ad(b, c)
			ad(a, c)
		q = []
		ones = []
		for i in range(n):
			if len(cnt[i]) == 1:
				ones.append(i)
		ans = []
		nans = []
		for i in range(n - 2):
			t = ones.pop()
			ind = cnt[t].pop()
			ans.append(ind + 1)
			cnt[triangles[ind][0]].discard(ind)
			cnt[triangles[ind][1]].discard(ind)
			cnt[triangles[ind][2]].discard(ind)
			if len(cnt[triangles[ind][0]]) == 1:
				ones.append(triangles[ind][0])
			if len(cnt[triangles[ind][1]]) == 1:
				ones.append(triangles[ind][1])
			if len(cnt[triangles[ind][2]]) == 1:
				ones.append(triangles[ind][2])
		dfs(0)
		print(*nans)
		print(*ans)
tt = threading.Thread(target=main)
tt.start()


def get_edge(vertex1, vertex2):
	return (vertex1, vertex2) if vertex1 < vertex2 else (vertex2, vertex1)

def swap(arr, i, j):
	temp = arr[i]
	arr[i] = arr[j]
	arr[j] = temp

def __starting_point():
	T = int(input())
	for t in range(T):
		n = int(input())
		pieces = []
		for c in range(n - 2):
			inp = input().rstrip().split(' ')
			pieces.append([int(inp[0]), int(inp[1]), int(inp[2])])
		G = {}
		piece_index = 0
		while piece_index < len(pieces):
			for vertex in pieces[piece_index]:
				if vertex not in G:
					G[vertex] = {}
				G[vertex][piece_index] = True
			piece_index += 1
		next_vertices = []
		for vertex in G:
			if len(G[vertex]) == 1:
				next_vertices.append(vertex)
		q = []
		border_edges = {}
		non_border_edges = {}
		while len(next_vertices) > 0:
			v = next_vertices.pop()
			if len(G[v]) > 0:
				piece_index = list(G[v].keys()).pop()
				q.append(str(piece_index + 1))
				piece = pieces[piece_index]
				G.pop(v)
				for vertex_index in range(3):
					vertex = piece[vertex_index]
					if vertex != v:
						G[vertex].pop(piece_index)
						if len(G[vertex]) == 1:
							next_vertices.append(vertex)
						edge = get_edge(v, vertex)
						if edge not in non_border_edges:
							border_edges[edge] = True
					else:
						swap(piece, 0, vertex_index)
				edge = get_edge(piece[1], piece[2])
				non_border_edges[edge] = True
		border_edges = list(border_edges.keys())
		vertices = {}
		for (a, b) in border_edges:
			if a not in vertices:
				vertices[a] = {}
			if b not in vertices:
				vertices[b] = {}
			vertices[a][b] = True
			vertices[b][a] = True
		start = None
		start_val = 5000000000
		for vertex in vertices:
			if len(vertices[vertex]) < start_val:
				start = vertex
				start_val = len(vertices[vertex])
		v = start
		p = []
		while len(p) < n:
			p.append(str(v))
			assert len(vertices[v]) <= 1
			if len(vertices[v]) == 1:
				neighbor = list(vertices[v].keys()).pop()
				vertices[neighbor].pop(v)
				v = neighbor
		print(' '.join(p))
		print(' '.join(q))
__starting_point()


import heapq
t = int(input())
for _ in range(t):
	n = int(input())
	counts = [0] * n
	triangles = [set() for _ in range(n)]
	assign_order = {}
	for i in range(n - 2):
		(a, b, c) = [x - 1 for x in list(map(int, input().split()))]
		t = (a, b, c)
		assign_order[t] = i
		for x in t:
			counts[x] += 1
			triangles[x].add(t)
	not_edges = set()
	edges = set()
	order = []
	que = [i for i in range(n) if counts[i] == 1]
	index = 0
	while index < n - 2:
		curr = que[index]
		tt = triangles[curr].pop()
		order.append(assign_order[tt])
		t = set(tt)
		t.remove(curr)
		(a, b) = (t.pop(), t.pop())
		for e in ((curr, a), (curr, b)):
			if e not in not_edges:
				edges.add(e)
		if index < n - 3:
			not_edges.add((a, b))
			not_edges.add((b, a))
		elif (a, b) not in not_edges:
			edges.add((a, b))
		for x in (a, b):
			counts[x] -= 1
			if counts[x] == 1:
				que.append(x)
			triangles[x].remove(tt)
		index += 1
	e = [[] for _ in range(n)]
	for (a, b) in edges:
		e[a].append(b)
		e[b].append(a)
	visited = [False] * n
	a = 0
	answer = []
	for i in range(n):
		visited[a] = True
		answer.append(a)
		for b in e[a]:
			if not visited[b]:
				a = b
				break
	print(' '.join(map(str, [x + 1 for x in answer])))
	print(' '.join(map(str, [x + 1 for x in order])))


from sys import stdin, stdout
from collections import deque
t = int(stdin.readline().strip())
lines = []
for _ in range(t):
	n = int(stdin.readline().strip())
	verts = {}
	pieces = {}
	for i in range(1, n - 2 + 1):
		(a, b, c) = stdin.readline().split()
		verts.setdefault(a, set()).add(i)
		verts.setdefault(b, set()).add(i)
		verts.setdefault(c, set()).add(i)
		pieces[i] = set([a, b, c])
	(root, r1, r2, rootp) = (None, None, None, None)
	for (v, s) in verts.items():
		if len(s) == 1:
			root = v
			rootp = s.copy().pop()
			rvs = pieces[rootp].copy()
			rvs.remove(root)
			r1 = rvs.pop()
			r2 = rvs.pop()
			break
	stk = deque([(0, root), (1, rootp), (0, r2), (2, r1, r2, rootp), (0, r1)])
	(vertord, pieceord) = ([], [])
	while stk:
		cmd = stk.pop()
		t = cmd[0]
		if t == 0:
			vertord.append(cmd[1])
		elif t == 1:
			pieceord.append(cmd[1])
		else:
			(_, v1, v2, p1) = cmd
			isect = verts[v1] & verts[v2]
			isect.remove(p1)
			if not isect:
				continue
			p2 = isect.pop()
			pvs = pieces[p2]
			pvs.remove(v1)
			pvs.remove(v2)
			v3 = pvs.pop()
			stk.append((1, p2))
			stk.append((2, v3, v2, p2))
			stk.append((0, v3))
			stk.append((2, v1, v3, p2))
	lines.append(' '.join(vertord) + '\n')
	lines.append(' '.join(map(str, pieceord)) + '\n')
stdout.writelines(lines)


class Union:

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

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

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.p[x] = y
				self.rank[y] += self.rank[x]
			else:
				self.p[y] = x
				self.rank[x] += self.rank[y]

def push(g, u, v):
	if u not in g:
		g[u] = []
	if v not in g:
		g[v] = []
	g[u].append(v)
	g[v].append(u)

def push_c(cnt, u, i):
	if u not in cnt:
		cnt[u] = set()
	cnt[u].add(i)

def process(cnt, tup, deg0, order, g, U, u):
	if len(cnt[u]) > 0:
		i = next(iter(cnt[u]))
	else:
		return
	for v in tup[i]:
		cnt[v].remove(i)
		if len(cnt[v]) == 1:
			deg0.append(v)
	(v, w) = (None, None)
	for x in tup[i]:
		if x == u:
			continue
		if v is None:
			v = x
		else:
			w = x
	order.append(i)
	if U.find(u) != U.find(v):
		U.union(u, v)
		push(g, u, v)
	if U.find(u) != U.find(w):
		U.union(u, w)
		push(g, u, w)

def solve():
	n = int(input())
	tup = [list(map(int, input().split())) for _ in range(n - 2)]
	g = {}
	cnt = {}
	order = []
	for (i, [u, v, w]) in enumerate(tup):
		push_c(cnt, u, i)
		push_c(cnt, v, i)
		push_c(cnt, w, i)
	U = Union(n)
	deg0 = [x for (x, num) in list(cnt.items()) if len(num) == 1]
	while len(deg0) > 0:
		u = deg0.pop()
		process(cnt, tup, deg0, order, g, U, u)
	used = [0] * (n - 2)
	for i in order:
		used[i] = 1
	for (i, x) in enumerate(used):
		if x == 0:
			order.append(i)
	circle = []
	used = [0] * (n + 1)
	for u in g:
		if len(g[u]) == 1:
			circle.append(u)
			used[u] = 1
			break
	i = 0
	while i < len(circle):
		u = circle[i]
		for v in g[u]:
			if used[v] == 0:
				used[v] = 1
				circle.append(v)
		i += 1
	print(' '.join([str(x) for x in circle]))
	print(' '.join([str(x + 1) for x in order]))
for _ in range(int(input())):
	solve()


import sys
from heapq import heappush, heappop
from collections import Counter, defaultdict
reader = (map(int, line.split()) for line in sys.stdin)

def insert(pq, value, entry_finder, push_id):
	entry = [value, push_id]
	entry_finder[push_id] = entry
	heappush(pq, entry)

def remove(entry_finder, push_id):
	entry = entry_finder.pop(push_id)
	entry[-1] = -1

def extract_min(pq, entry_finder):
	while pq:
		(value, push_id) = heappop(pq)
		if push_id > 0:
			del entry_finder[push_id]
			return (push_id, value)
	return (-1, '*')
(t,) = next(reader)
for test in range(t):
	(n,) = next(reader)
	pq = []
	entry_finder = {}
	triangle = [tuple(next(reader)) for _ in range(n - 2)]
	deg = Counter()
	v_tri = defaultdict(list)
	used = set()
	for (i, tri) in enumerate(triangle):
		for v in tri:
			deg[v] += 1
			v_tri[v].append(i)
	for (v, value) in deg.items():
		insert(pq, value, entry_finder, push_id=v)
	g = [set() for _ in range(n + 1)]
	ansQ = []
	for _ in range(n - 2):
		(v, value) = extract_min(pq, entry_finder)
		while True:
			i = v_tri[v].pop()
			if i not in used:
				break
		used.add(i)
		ansQ.append(i + 1)
		tri = triangle[i]
		tos = [to for to in tri if to != v]
		for to in tos:
			if to in g[v]:
				g[v].remove(to)
				g[to].remove(v)
			else:
				g[v].add(to)
				g[to].add(v)
			deg[to] -= 1
			remove(entry_finder, push_id=to)
			insert(pq, deg[to], entry_finder, push_id=to)
		(to1, to2) = tos
		if to1 in g[to2]:
			g[to1].remove(to2)
			g[to2].remove(to1)
		else:
			g[to1].add(to2)
			g[to2].add(to1)
	ansP = []
	visited = [False] * (n + 1)
	s = 1
	stack = [s]
	while stack:
		v = stack.pop()
		if not visited[v]:
			visited[v] = True
			ansP.append(v)
			for to in g[v]:
				stack.append(to)
	print(*ansP)
	print(*ansQ)