A sequence of $n$ numbers is called permutation if it contains all integers from $1$ to $n$ exactly once. For example, the sequences [$3, 1, 4, 2$], [$1$] and [$2,1$] are permutations, but [$1,2,1$], [$0,1$] and [$1,3,4$] — are not.

Kristina had a permutation $p$ of $n$ elements. She wrote it on the whiteboard $n$ times in such a way that:

while writing the permutation at the $i$-th ($1 \le i \le n)$ time she skipped the element $p_i$

So, she wrote in total $n$ sequences of length $n-1$ each.

For example, suppose Kristina had a permutation $p$ = $[4,2,1,3]$ of length $4$. Then she did the following:

Wrote the sequence $[2, 1, 3]$, skipping the element $p_1=4$ from the original permutation.

Wrote the sequence $[4, 1, 3]$, skipping the element $p_2=2$ from the original permutation.

Wrote the sequence $[4, 2, 3]$, skipping the element $p_3=1$ from the original permutation.

Wrote the sequence $[4, 2, 1]$, skipping the element $p_4=3$ from the original permutation.

You know all $n$ of sequences that have been written on the whiteboard, but you do not know the order in which they were written. They are given in arbitrary order. Reconstruct the original permutation from them.

For example, if you know the sequences $[4, 2, 1]$, $[4, 2, 3]$, $[2, 1, 3]$, $[4, 1, 3]$, then the original permutation will be $p$ = $[4, 2, 1, 3]$.


-----Input-----

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains one integer $n$ ($3 \le n \le 100$).

This is followed by $n$ lines, each containing exactly $n-1$ integers and describing one of the sequences written out on the whiteboard.

It is guaranteed that all sequences could be obtained from some permutation $p$, and that the sum $n^2$ over all input sets does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output on a separate line a permutation $p$ such that the given $n$ sequences could be obtained from it.

It is guaranteed that the answer exists and it is the only one. In other words, for each test case the required permutation is sure to exist.


-----Examples-----

Input
5
4
4 2 1
4 2 3
2 1 3
4 1 3
3
2 3
1 3
1 2
5
4 2 1 3
2 1 3 5
4 2 3 5
4 1 3 5
4 2 1 5
4
2 3 4
1 3 4
1 2 3
1 2 4
3
2 1
1 3
2 3
Output
4 2 1 3 
1 2 3 
4 2 1 3 5 
1 2 3 4 
2 1 3


-----Note-----

The first test case is described in the problem statement.

In the second test case, the sequences are written in the correct order.

Difficulty: EASY
Tags: Mathematics

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	perms = []
	for _ in range(n):
		perms.append(list(input().split()))
	start = None
	if perms[0][0] == perms[1][0] or perms[0][0] == perms[2][0]:
		start = perms[0][0]
	else:
		start = perms[1][0]
	for perm in perms:
		if perm[0] != start:
			print(start + ' ' + ' '.join(perm))
			break


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	ans = []
	l = []
	for i in range(n):
		l.append(sys.stdin.readline().split())
	for i in range(n):
		for j in range(i + 1, n):
			if l[i][1] != l[j][1] or l[i][0] == l[j][0]:
				continue
			else:
				temp = j - 1
				if temp == i:
					temp = (j + 1) % n
				if l[temp][0] == l[j][0]:
					ans = [l[j][0]] + l[i]
				else:
					ans = [l[i][0]] + l[j]
				break
	print(' '.join(ans))


m = []
n = int(input())
for i in range(n):
	k = int(input())
	a = input()
	b = a.split()[0]
	c = 0
	d = []
	d.append(a)
	for j in range(k - 1):
		a1 = input()
		if b != a1.split()[0]:
			d.append(a1)
			b1 = a1.split()[0]
		else:
			c = c + 1
	if c == 0:
		m.append(b1 + ' ' + d[0])
	else:
		m.append(b + ' ' + d[1])
for i in m:
	print(i)


import sys
input = sys.stdin.readline
s = set()
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	if a[0] == b[0]:
		corr = a[0]
	elif b[0] == c[0]:
		corr = b[0]
	elif a[0] == c[0]:
		corr = a[0]
	if a[0] != corr:
		for i in range(n - 3):
			input()
		print(str(corr), ' '.join(list(map(str, a))))
	elif b[0] != corr:
		for i in range(n - 3):
			input()
		print(str(corr), ' '.join(list(map(str, b))))
	elif c[0] != corr:
		for i in range(n - 3):
			input()
		print(str(corr), ' '.join(list(map(str, c))))
	else:
		for i in range(n - 3):
			inp = list(map(int, input().split()))
			if inp[0] != corr:
				a = inp
		print(str(corr), ' '.join(list(map(str, a))))


import sys
input = sys.stdin.readline
out = []
for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		buf = [int(i) for i in input().split()]
		a.append(buf)
	p0 = [i[0] for i in a]
	p0.sort()
	if p0[0] == p0[1]:
		(u, c) = (p0[-1], p0[0])
	else:
		(u, c) = (p0[0], p0[-1])
	for i in a:
		if i[0] == u:
			ans = [c] + i
			break
	out.append(ans)
for i in out:
	print(*i)


def main():
	test = int(input())
	for _ in range(test):
		n = int(input())
		lst = []
		i = 0
		while i < n:
			lst.append(input().split())
			i += 1
		i = 1
		while i < len(lst):
			if lst[i][0] != lst[i - 1][0]:
				break
			i += 1
		answer = ''
		if i == 1 and lst[1][0] == lst[2][0]:
			answer = lst[i][0] + ' ' + ' '.join(lst[0])
		else:
			answer = lst[i - 1][0] + ' ' + ' '.join(lst[i])
		print(answer)
main()


def program():
	n = int(input())
	table = []
	count_one = 0
	count_two = 0
	first_encounter = -1
	scnd_encounter = -1
	target = -1
	for i in range(0, n):
		table.append([int(x) for x in input().split()])
		if i == 0:
			first_encounter = table[i][0]
			count_one = 1
		elif table[i][0] == first_encounter:
			count_one += 1
		else:
			scnd_encounter = table[i][0]
			count_two = +1
		if count_one != 0 and count_two != 0:
			if count_one > count_two:
				target = scnd_encounter
			else:
				target = first_encounter
	for i in range(0, n):
		if table[i][0] == target:
			a = [str(x) for x in table[i]]
			b = str(first_encounter)
			c = str(scnd_encounter)
			if count_one > count_two:
				return b + ' ' + ' '.join(a)
			else:
				return c + ' ' + ' '.join(a)
			break
t = int(input())
answers = []
for i in range(0, t):
	answers.append(program())
for i in answers:
	print(i)


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
	n = inp()
	a = []
	for i in range(n):
		l = [int(k) for k in inps()]
		a.append(l)
	k = a[0][0]
	d = {}
	for i in a:
		d[i[0]] = d.get(i[0], 0) + 1
	for i in a:
		if d[i[0]] == 1:
			ans = i
	for i in d:
		if d[i] > 1:
			k = [i]
	k.extend(ans)
	for i in k:
		print(i, end=' ')
	print()

def main():
	testcases = 1
	testcases = inp()
	for t in range(testcases):
		solve()

def inp():
	return int(input())

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


import sys

def solve():
	n = int(data.readline())
	all = {k: 0 for k in range(1, n + 1)}
	for _ in range(n):
		row = list(map(int, data.readline().split()))
		for (i, x) in enumerate(row):
			all[x] += i
	print(*sorted(all.keys(), key=lambda k: all[k]))
data = sys.stdin
total_tests = int(data.readline())
for test in range(total_tests):
	solve()


def solve():
	n = inp()
	permSize = [0] * n
	perm = []
	for i in range(0, n):
		permSize[i] = inp()
		permList = []
		for i in range(0, permSize[i]):
			permList.append(inlt())
		perm.append(permList)
	for i in range(0, n):
		miss = perm[i][0][0]
		start = perm[i][1][0]
		if miss == start:
			for j in range(2, permSize[i]):
				if perm[i][j][0] != start:
					break
		elif start != perm[i][2][0]:
			start = miss
			miss = perm[i][1][0]
			j = 1
		else:
			j = 0
		print(start, end=' ')
		print(' '.join(map(str, perm[i][j])))

def main():
	solve()

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())
main()


from collections import Counter
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	N = int(input())
	arrs = []
	for __ in range(N):
		arrs.append(list(map(int, input().split())))
	end = []
	for i in range(N):
		end.append(arrs[i][-1])
	end = Counter(end)
	end = sorted(end.items(), key=lambda x: x[1])
	Min = end[0][0]
	Max = end[1][0]
	for i in range(N):
		if arrs[i][-1] == Min:
			result = arrs[i]
			result.append(Max)
			break
	print(' '.join(map(str, result)))


def solve(p):
	v = [p[0][0], p[1][0], p[2][0]]
	vb = v[0]
	if v.count(vb) == 1:
		vb = v[1]
	for i in range(len(p)):
		if p[i][0] != vb:
			res = p[i].copy()
			res.insert(0, vb)
			return res
	return []
t = int(input())
ans = []
for ti in range(t):
	n = int(input())
	p = []
	for ni in range(n):
		p.append([int(x) for x in input().split()])
	ans.append(solve(p))
for a in ans:
	print(' '.join([str(x) for x in a]))


def sol(n, l):
	set1 = set()
	start = ''
	for a in range(3):
		if l[a][0] in set1:
			start = l[a][0]
		set1.add(l[a][0])
	if len(set1) == 3:
		i = 0 if l[0][0] != start else 1
		return start + ' '.join(l[i])
	for a in l:
		if a[0] != start:
			return start + ' ' + ' '.join(a)
	return None
t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for _ in range(n):
		l.append(input().split())
	print(sol(n, l))


t = int(input())
for e in range(t):
	n = int(input())
	x = []
	r = p = a = ''
	for i in range(n):
		q = input()
		x.append(q)
		if i < 3:
			for w in x[i]:
				if w != ' ' and i == 0:
					r += w
				elif w != ' ' and i == 1:
					p += w
				elif w != ' ' and i == 2:
					a += w
				else:
					break
	c = ''
	if r == p:
		c = r
	elif p == a:
		c = p
	else:
		c = a
	u = ''
	for i in x:
		u = ''
		for w in i:
			if w != ' ':
				u += w
			else:
				break
		if u != c:
			print(c + ' ' + i)
			break


t = int(input())
for i in range(t):
	a = []
	n = int(input())
	for j in range(n):
		a.append(input().split())
	b = []
	if a[0][0] == a[1][0] or a[0][0] == a[2][0]:
		b.append(a[0][0])
	elif a[1][0] == a[2][0]:
		b.append(a[1][0])
	for j in range(n - 1):
		f = True
		for k in range(n):
			if a[k][j] != b[j]:
				b.append(a[k][j])
				f = False
				break
		if f:
			b.append(b[j])
	print(' '.join(b))


import math
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	tree = []
	for i in range(n):
		tree.append([])
	for i in range(n):
		tree[i] = list(map(int, input().split()))
	if tree[0][0] == tree[1][0]:
		a = tree[0][0]
		b = 0
	elif tree[0][0] == tree[2][0]:
		a = tree[0][0]
		b = 0
	else:
		a = tree[1][0]
		b = 1
	for i in range(n):
		if tree[i][0] != a:
			ans = i
			break
	print(a, end=' ')
	for i in range(n - 1):
		print(tree[ans][i], end=' ')
	print()


def get(a):
	b = ''
	for x in a:
		if x == ' ':
			return b
		else:
			b = b + x
for x in range(int(input())):
	y = int(input())
	a = input()
	b = input()
	c = input()
	e = True
	if get(a) == get(b) and get(b) == get(c):
		for z in range(y - 3):
			d = input()
			if e:
				if get(d) != get(a):
					c = d
					e = False
		print(get(a) + ' ' + c)
	elif get(a) == get(b) and get(b) != get(c):
		for z in range(y - 3):
			d = input()
		print(get(a) + ' ' + c)
	elif get(a) == get(c) and get(b) != get(c):
		for z in range(y - 3):
			d = input()
		print(get(a) + ' ' + b)
	elif get(b) == get(c) and get(b) != get(a):
		for z in range(y - 3):
			d = input()
		print(get(c) + ' ' + a)


from math import pi

def sample():
	n = int(input())
	a = [input() for i in range(n)]
	d = {}
	for item in a:
		first = item.split()[0]
		if first not in d:
			d.update({first: (0, item)})
		d[first] = (d[first][0] + 1, d[first][1])
	keys = list(d.keys())
	if d[keys[0]][0] != n - 1:
		keys.reverse()
	print(d[keys[0]][1].split()[0] + ' ' + d[keys[1]][1])
t = int(input())
for task in range(t):
	sample()


t = input()
t = int(t)
while t > 0:
	t -= 1
	n = input()
	n = int(n)
	c = []
	d = {}
	for i in range(n):
		c.append(input().split())
	for i in range(n):
		a = c[i][0]
		if d.get(a) == None:
			d[a] = 1
		else:
			d[a] += 1
	ans = []
	for i in d:
		if d[i] == 1:
			for j in range(n):
				if c[j][0] == i:
					ans = ans + c[j]
		else:
			ans = [i] + ans
	print(' '.join(ans))


for _ in range(int(input())):
	n = int(input())
	arr = []
	for _ in range(n):
		temp = input().split(' ')
		arr.append(temp)
	ans = []
	temp = arr[0][0]
	curr = temp
	if arr[1][0] != temp and arr[2][0] != temp:
		curr = arr[1][0]
	ans.append(curr)
	for i in range(n - 1):
		for j in range(n):
			if arr[j][i] != curr:
				curr = arr[j][i]
				ans.append(curr)
				break
	print(' '.join(ans))


import sys
from math import *
from collections import defaultdict, deque
input = sys.stdin.readline
mod = 10 ** 9 + 7
INF = 1061109567
N = int(2 * 10 ** 5 + 5)
LINF = 4557430888798830399

def solve():
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	cnt = [0] * (n + 1)
	(num, idx) = (0, 0)
	for i in range(n):
		cnt[a[i][0]] += 1
		if cnt[a[i][0]] >= idx:
			idx = cnt[a[i][0]]
			num = a[i][0]
	for i in range(n):
		if a[i][0] != num:
			print(num, end=' ')
			for j in range(n - 1):
				print(a[i][j], end=' ')
			print()
			break
T = int(input())
for t in range(T):
	solve()


import sys
input = sys.stdin.readline

def solve_c():
	answ = []
	perms = {}
	n = int(input())
	for i in range(n):
		perm = list(map(int, input().split()))
		for j in range(n - 1):
			val = perm[j]
			if j not in perms:
				perms[j] = [[val, 1]]
			else:
				mas = perms[j]
				if mas[0][0] == val:
					mas[0][1] += 1
				elif len(mas) == 1:
					mas.append([val, 1])
				else:
					mas[1][1] += 1
	val = 0
	a = perms[0][0][1]
	b = perms[0][1][1]
	if a > b:
		val = perms[0][0][0]
	else:
		val = perms[0][1][0]
	answ.append(val)
	for i in range(n - 1):
		mas = perms[i]
		if mas[0][0] == answ[i]:
			answ.append(mas[1][0])
		else:
			answ.append(mas[0][0])
	return answ

def main():
	for _ in range(int(input())):
		answ = solve_c()
		print(*answ)
main()


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	res = sorted((input().strip().split(maxsplit=1) for _ in range(n)))
	if res[0][0] == res[1][0]:
		print(res[0][0], res[-1][0], res[-1][1])
	else:
		print(res[1][0], res[0][0], res[0][1])


def main():
	_i = int(input())
	for _ in range(_i):
		n = int(input().strip('\r\n'))
		a1 = [int(x) for x in input().strip('\r\n').split()]
		a2 = [int(x) for x in input().strip('\r\n').split()]
		skip = 2
		if a1[0] == a2[0]:
			a3 = list(a2)
			while a3[0] == a2[0]:
				a3 = [int(x) for x in input().strip('\r\n').split()]
				skip += 1
		else:
			a3 = [int(x) for x in input().strip('\r\n').split()]
			skip += 1
		for _ in range(n - skip):
			_ = [int(x) for x in input().strip('\r\n').split()]
		if a1[0] == a2[0]:
			res = [a1[0]] + a3
		elif a1[0] == a3[0]:
			res = [a1[0]] + a2
		else:
			res = [a2[0]] + a1
		print(' '.join([str(x) for x in res]))
main()


t = int(input())
for _ in range(0, t):
	n = int(input())
	lists = []
	for i in range(0, n):
		lists.append([num for num in input().split()])
	last1 = lists[0][n - 2]
	last2 = lists[1][n - 2]
	last3 = lists[2][n - 2]
	if last1 == last2:
		last = str(last1)
	elif last1 == last3:
		last = str(last1)
	else:
		last = str(last2)
	for list1 in lists:
		if list1[n - 2] != last:
			s = ''
			for num in list1:
				s += str(num) + ' '
			s += str(last)
			break
	print(s)


def solve():
	number_of_them = int(input())
	vals = []
	for i in range(number_of_them):
		vals.append([int(_) for _ in input().split()])
	first_element = {}
	what_we_are_looking_for = None
	for i in range(3):
		element = vals[i][0]
		if element in first_element:
			what_we_are_looking_for = element
			break
		else:
			first_element[element] = 1
	i = 0
	while i < number_of_them:
		if vals[i][0] == what_we_are_looking_for:
			i += 1
		else:
			return [what_we_are_looking_for] + vals[i]
	return []
n = int(input())
for j in range(n):
	res = solve()
	print(' '.join([str(_) for _ in res]))


testcases = int(input())
for i in range(testcases):
	n = int(input())
	perm = list()
	for j in range(2):
		inp = list(map(int, input().split()))
		perm.append(inp)
		if j == 0:
			first_0 = inp[0]
		if j == 1:
			first_1 = inp[0]
			if first_0 == first_1:
				start_found = True
				start = first_0
				for j in range(2, n):
					inp = list(map(int, input().split()))
					if inp[0] != start:
						output = [start] + inp
			else:
				start_found = False
				inp = list(map(int, input().split()))
				if inp[0] == first_0:
					output = [first_0] + perm[1]
				else:
					output = [first_1] + perm[0]
				for j in range(3, n):
					inp = list(map(int, input().split()))
	print(' '.join(map(str, output)))


for _ in range(int(input())):
	n = int(input())
	matrix = []
	matrix.append(list(input().split()))
	(a, b) = (matrix[0][0], 0)
	(a_freq, b_freq) = (1, 0)
	for i in range(n - 1):
		matrix.append(list(input().split()))
		if matrix[-1][0] == a:
			a_freq += 1
		else:
			b = matrix[-1][0]
			b_freq += 1
	first_ele = a if a_freq > b_freq else b
	for i in range(n):
		if matrix[i][0] != first_ele:
			seq = ' '.join(matrix[i])
	seq = first_ele + ' ' + seq
	print(seq)


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	n = int(input())
	(l, l1) = ([], [])
	for i in range(n):
		s = list(map(int, input().split()))
		l.append(s)
		l1.append(l[i][0])
	u = list(set(l1))
	a = {}
	for i in u:
		a[i] = l1.count(i)
	m = max(a, key=a.get)
	s1 = [m]
	for i in range(n):
		if l[i][0] != m:
			for i in l[i]:
				s1.append(i)
			break
	for i in s1:
		print(i, end=' ')
	print()
	t -= 1


def solve():
	n = int(input())
	arr = []
	for _ in range(n):
		t = list(map(int, input().split()))
		arr.append(t)
	ff = []
	for i in range(3):
		ff.append(arr[i][0])
	ff.sort()
	firstval = ff[1]
	for i in range(n):
		if arr[i][0] != firstval:
			print(firstval, *arr[i])
			break
for _ in range(int(input())):
	solve()


for sol in range(int(input())):
	d = dict()
	ans = ''
	n = int(input())
	for i in range(n):
		lst = input().split()
		if lst[0] in d:
			d[lst[0]][0] += 1
		else:
			d[lst[0]] = [1, lst]
	p = []
	for el in d.keys():
		p.append(d[el])
	if p[0][0] < p[1][0]:
		print(str(p[1][1][0]), end=' ')
		for el in p[0][1]:
			print(el, end=' ')
		print()
	else:
		print(str(p[0][1][0]), end=' ')
		for el in p[1][1]:
			print(el, end=' ')
		print()


def check(line1, lines):
	for line2 in lines:
		x = line1.index(list(set(line1) - set(line2))[0])
		if line1[:x] + line1[x + 1:] != line2:
			return False
	return True
ans = []
for t in range(int(input())):
	n = int(input())
	line = input().split()
	lines = [input().split() for _ in range(n - 1)]
	num = list(set(map(str, range(1, len(line) + 2))) - set(line))
	for i in range(len(line) + 1):
		line1 = line[:i] + num + line[i:]
		if check(line1, lines):
			ans.append(' '.join(line1))
			break
print('\n'.join(ans))


first = 0
for i in range(int(input())):
	n = int(input())
	spisok = [list(map(int, input().split())) for i in range(n)]
	if spisok[0][0] == spisok[1][0]:
		first = spisok[0][0]
	else:
		first = spisok[2][0]
	for i in range(n):
		if spisok[i][0] != first:
			print(first, *spisok[i])


n = int(input())
for _ in range(n):
	m = int(input())
	vals = [list(map(int, input().split())) for _ in range(m)]
	if vals[0][0] == vals[1][0]:
		for x in vals:
			if x[0] != vals[0][0]:
				r = [vals[0][0]] + x
	elif vals[1][0] == vals[2][0]:
		r = [vals[1][0]] + vals[0]
	else:
		r = [vals[0][0]] + vals[1]
	t = ''
	for x in r:
		t = t + str(x) + ' '
	print(t[:-1])


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for i in range(n):
		a = list(map(int, input().split()))
		l.append(a)
	l.sort()
	f = l[1][0]
	if f == l[0][0]:
		ans = l[-1]
		ans.insert(0, f)
	else:
		ans = l[0]
		ans.insert(0, f)
	for i in range(n - 1):
		print(ans[i], end=' ')
	print(ans[-1])


t = int(input())
for ncase in range(1, t + 1):
	n = int(input())
	s = []
	for i in range(n):
		s.append([int(i) for i in input().split(' ')])
	ans = []
	if s[0][0] == s[1][0]:
		ans.append(s[0][0])
	else:
		ans.append(s[2][0])
	for i in range(n):
		if s[i][0] != ans[0]:
			ans += s[i]
	print(' '.join([str(i) for i in ans]))


import sys

def main():
	tc = int(input())
	for _ in range(tc):
		n = int(input())
		arr = [[int(a) for a in input().split()] for i in range(n)]
		ini = arr[0][0]
		j = n - 1
		for i in range(1, n):
			if ini == arr[i][0]:
				j = i
			elif ini != arr[i][0]:
				break
		ans = []
		ans.append(arr[j][0])
		if ini == arr[j][0]:
			ans += arr[i]
		else:
			ans += arr[0]
		print(*ans)
main()


for _ in range(int(input())):
	n = int(input())
	perms = []
	for _ in range(n):
		l = list(map(int, input().split()))
		perms.append(l)
	perms.sort()
	if perms[0][0] == perms[1][0]:
		print(perms[0][0], *perms[-1])
	else:
		print(perms[1][0], *perms[0])


R = lambda : [*map(int, input().split())]
for _ in [0] * R()[0]:
	(a, b, *_, c) = sorted((R() for _ in [0] * R()[0]))
	print(*(c[:1] + a, a[:1] + c)[a[0] == b[0]])


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = []
	for _ in range(n):
		l.append([i for i in input().split(' ')])
	i = 0
	for i in range(n - 1):
		if not l[i][n - 2] == l[i + 1][n - 2]:
			break
	if i < n - 2:
		if l[i][n - 2] == l[i + 2][n - 2]:
			l[i + 1].append(l[i][n - 2])
			print(*l[i + 1])
		if l[i + 1][n - 2] == l[i + 2][n - 2]:
			l[i].append(l[i + 1][n - 2])
			print(*l[i])
	else:
		if l[i][n - 2] == l[i - 1][n - 2]:
			l[i + 1].append(l[i][n - 2])
			print(*l[i + 1])
		if l[i + 1][n - 2] == l[i - 1][n - 2]:
			l[i].append(l[i + 1][n - 2])
			print(*l[i])


for i in range(int(input())):
	n = int(input())
	total = []
	for j in range(n):
		total.append([int(x) for x in input().split()])
	if total[0][0] == total[1][0] or total[0][0] == total[2][0]:
		first = total[0][0]
	else:
		first = total[1][0]
	for j in range(n):
		if total[j][0] != first:
			print(first, *total[j])
			break


t = int(input())
for i in range(t):
	n = int(input())
	count = 0
	work = 0
	for j in range(n):
		numbers = [int(num) for num in input().split(' ', n - 2)]
		if work == 0:
			if j == 0:
				k1 = numbers[0]
				ans1 = numbers
			elif j == 1 and numbers[0] != k1:
				k2 = numbers[0]
				ans2 = numbers
				count += 1
			elif j == 2 and count == 1 and (numbers[0] != k1):
				ans1.insert(0, k2)
				print(' '.join([str(elem) for elem in ans1]))
				work = 1
			elif j == 2 and count == 1 and (numbers[0] == k1):
				ans2.insert(0, k1)
				print(' '.join([str(elem) for elem in ans2]))
				work = 1
			elif numbers[0] != k1:
				numbers.insert(0, k1)
				print(' '.join([str(elem) for elem in numbers]))
				work = 1


def func():
	n = int(input())
	lt = []
	for i in range(n):
		lt.append(list(map(int, input().split())))
	ans = lt[0]
	a = n * (n + 1) // 2 - sum(ans)
	mn = n
	mx = 0
	for i in range(1, n):
		for j in range(n - 1):
			if lt[i][j] == a:
				mn = min(mn, j)
				mx = max(mx, j)
	if mx == 0:
		ans.insert(0, a)
	else:
		ans.insert(mn + 1, a)
	print(' '.join(map(str, ans)))
for i in range(int(input())):
	func()


def solve():
	n = int(input())
	l = []
	for i in range(n):
		a = list(map(int, input().split()))
		l.append(a)
	ans = []
	fuck = []
	for i in range(len(l)):
		fuck.append(l[i][0])
	suck = list(set(fuck))
	a = 0
	if fuck.count(suck[0]) == 1:
		a = suck[1]
		for i in range(len(fuck)):
			if fuck[i] == suck[0]:
				ans = l[i]
				break
	else:
		a = suck[0]
		for i in range(len(fuck)):
			if fuck[i] == suck[1]:
				ans = l[i]
				break
	print(a, *ans)
for _ in range(int(input())):
	solve()


def yj(m):
	n1 = dict()
	for i in range(3):
		n1[m[i][0]] = n1.get(m[i][0], 0) + 1
	k = 0
	for i in n1.items():
		if i[1] > 1:
			k = i[0]
			break
	s = 0
	for i in m:
		if i[0] != k:
			s = i
			break
	return [k] + s
t = int(input())
for i in range(t):
	n = int(input())
	m = []
	for i in range(n):
		m.append(list(map(int, input().split())))
	print(*yj(m))


def solution(n, seq, fir):
	(maxi, mini) = (max(fir), min(fir))
	ind1 = fir.index(maxi)
	ind2 = fir.index(mini)
	if fir.count(maxi) > 1:
		res = [maxi] + seq[ind2]
	else:
		res = [mini] + seq[ind1]
	print(' '.join(map(str, res)))
	return
t = int(input())
for _ in range(t):
	n = int(input())
	seq = []
	fir = []
	for i in range(n):
		s = list(map(int, input().split()))
		seq.append(s)
		fir.append(s[0])
	solution(n, seq, fir)


t = int(input())
for i in range(t):
	n = int(input())
	l = [None] * n
	for i in range(n):
		l[i] = list(map(int, input().split()))
	a = l[0][0]
	count = 1
	for i in range(1, len(l)):
		if l[i][0] == a:
			count += 1
		else:
			b = i
	if count == 1:
		a = l[1][0]
		b = 0
	output = str(a)
	for i in range(len(l[b])):
		output += ' '
		output += str(l[b][i])
	print(output)


for t in range(int(input())):
	n = int(input())
	num_list = []
	fir = []
	for i in range(n):
		a = input().split()
		num_list.append(a)
		fir.append(a[0])
	fir.sort()
	ans = ['0'] * n
	if fir.count(fir[0]) > fir.count(fir[-1]):
		ans[0] = fir[0]
	else:
		ans[0] = fir[-1]
	for i in range(n - 1):
		c = []
		for j in num_list:
			if j[i] != ans[i]:
				ans[i + 1] = j[i]
	print(*ans)


t = int(input())
for i in range(t):
	s = int(input())
	a = []
	b = []
	k = 0
	x = []
	for j in range(s):
		z = list(map(int, input().split()))
		b.append(z)
		a.append(z[0])
		if j >= 2 and a.count(z[0]) == 1 and (k == 0):
			k = z[0]
			x = b[-1]
	if k != 0:
		print(a[0], *x)
	elif a.count(a[0]) == 1:
		print(a[1], *b[0])
	else:
		print(a[0], *b[1])


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for j in range(n):
		tmp = list(input().split(' '))
		a.append(tmp)
	b = a[0][n - 2]
	if a[1][n - 2] == b:
		last = b
	else:
		last = a[2][n - 2]
	for k in range(n):
		if a[k].count(last) == 0:
			for ii in range(n - 1):
				print(a[k][ii], end=' ')
			print(last)
			break


for jj in range(int(input())):
	n = int(input())
	grid = []
	for i in range(n):
		a = [int(i) for i in input().split()]
		grid.append(a)
	if grid[0][0] == grid[1][0]:
		for j in range(2, n):
			if grid[j][0] != grid[0][0]:
				print(*[grid[0][0]] + grid[j])
				break
	elif grid[2][0] == grid[0][0]:
		print(*[grid[2][0]] + grid[1])
	else:
		print(*[grid[2][0]] + grid[0])


t = int(input())
for _ in range(t):
	n = int(input())
	p = [list(map(int, input().split())) for _ in range(n)]
	count = [0] * (n + 1)
	for pi in p:
		count[pi[0]] += 1
	f = count.index(max(count))
	print(f, end=' ')
	for pi in p:
		if pi[0] != f:
			print(*pi)


n = int(input())
for i in range(n):
	nn = int(input())
	res = []
	tres_listas = []
	primer_numero = 0
	for j in range(3):
		tres_listas.append([int(k) for k in input().split()])
	if tres_listas[0][0] == tres_listas[1][0] and tres_listas[0][0] != tres_listas[2][0]:
		primer_numero = tres_listas[0][0]
		res = [primer_numero] + tres_listas[2]
	elif tres_listas[0][0] == tres_listas[1][0]:
		primer_numero = tres_listas[0][0]
	elif tres_listas[0][0] == tres_listas[2][0]:
		primer_numero = tres_listas[0][0]
		res = [primer_numero] + tres_listas[1]
	else:
		primer_numero = tres_listas[1][0]
		res = [primer_numero] + tres_listas[0]
	for j in range(3, nn):
		lista = [int(k) for k in input().split()]
		if lista[0] != primer_numero:
			res = [primer_numero] + lista
	res = [str(i) for i in res]
	print(' '.join(res))


cases = int(input())
for i in range(cases):
	n = int(input())
	p = []
	for j in range(n):
		p.append(list(map(int, input().split())))
	p.sort()
	if p[0][0] == p[1][0]:
		print(p[0][0], *p[n - 1])
	else:
		print(p[1][0], *p[0])


t = int(input())
for _ in range(t):
	n = int(input())
	a = [[int(x) for x in input().split()] for _ in range(n)]
	if a[0][0] == a[1][0] or a[0][0] == a[2][0]:
		x = a[0][0]
	else:
		x = a[1][0]
	k = 0
	while a[k][0] == x:
		k += 1
	ans = a[k]
	print(str(x) + ' ' + ' '.join(map(str, ans)))


def ii(num=False):
	i = input().split()
	if num:
		return int(i[0])
	try:
		return list(map(int, i))
	except Exception:
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(ii(1)):
	n = ii(1)
	matrix = []
	for i in range(n):
		matrix.append(ii())
	if matrix[0][0] != matrix[1][0] and matrix[1][0] == matrix[2][0]:
		print(matrix[1][0], *matrix[0])
	else:
		first = matrix[0][0]
		for i in range(n):
			if matrix[i][0] != first:
				print(first, *matrix[i])
				break


T = int(input())
for tc in range(T):
	n = int(input())
	x = []
	for i in range(n):
		l = list(map(int, input().split()))
		x.append(l)
	x.sort()
	if x[0][0] == x[1][0]:
		print(x[0][0], *x[-1])
	else:
		print(x[1][0], *x[0])


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	a.sort()
	if a[0][0] == a[1][0]:
		print(a[0][0], *a[-1])
	else:
		print(a[1][0], *a[0])


for i in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	f = c[0]
	count = 1
	sum = 0
	for i in range(n - 1):
		a = list(map(int, input().split()))
		if a[0] == f:
			count += 1
			b = a
		else:
			sum += 1
			d = a
	if count > sum:
		print(f, ' '.join(list(map(str, d))))
	else:
		print(d[0], ' '.join(list(map(str, c))))


from collections import defaultdict

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		rec = defaultdict(list)
		seqs = []
		for _ in range(n):
			seqs.append(list(map(int, input().split())))
			rec[seqs[-1][0]].append(len(seqs) - 1)
		(ans, idx) = ([], -1)
		for (k, v) in rec.items():
			if len(v) == 1:
				idx = v[0]
			else:
				ans.append(k)
		ans.extend(seqs[idx])
		print(' '.join(map(str, ans)))
main()


for t in range(int(input())):
	n = int(input())
	l = []
	d = {}
	while n > 0:
		nums = list(map(int, input().split()))
		d[n, nums[0]] = nums
		l.append(nums[0])
		n -= 1
	l = sorted(l)
	if l.count(l[0]) > 1:
		f = l[0]
		s = l[-1]
	else:
		f = l[-1]
		s = l[0]
	for key in d:
		if key[1] == s:
			l = [f]
			l.extend(d[key])
			break
	l = [str(num) for num in l]
	s = ' '.join(l)
	print(s)


a = int(input())
for i in range(a):
	b = int(input())
	m = list(map(int, input().split()))
	n = list(map(int, input().split()))
	pnt = 0
	if m[0] != n[0] and m[1] != n[1] and (pnt == 0):
		if m[0] == n[1]:
			print(n[0], *m)
			pnt = 1
		else:
			print(m[0], *n)
			pnt = 1
	for j in range(b - 2):
		g = list(map(int, input().split()))
		if m[0] != g[0] and m[1] != g[1] and (pnt == 0):
			if m[0] == g[1]:
				print(g[0], *m)
				pnt = 1
			else:
				print(m[0], *g)
				pnt = 1
		elif n[0] != g[0] and n[1] != g[1] and (pnt == 0):
			if n[0] == g[1]:
				print(g[0], *n)
				pnt = 1
			else:
				print(n[0], *g)
				pnt = 1


for _ in range(int(input())):
	n = int(input())
	res = []
	cnt = [0] * n
	p = []
	ans = []
	for i in range(n):
		k = [int(i) for i in input().split()]
		if k[0] not in p:
			res.append(k)
			p.append(k[0])
		cnt[k[0] - 1] += 1
	k = cnt.index(max(cnt)) + 1
	if res[0][0] == k:
		print(res[0][0], end=' ')
		print(*res[1])
	else:
		print(res[1][0], end=' ')
		print(*res[0])


for __ in range(int(input())):
	(l, head) = ([], [])
	for _ in range(int(input())):
		l.append(list(map(int, input().split())))
		head.append(l[-1][0])
	s = sorted(head)
	if s[0] != s[1]:
		i = head.index(s[0])
		print(s[1], end=' ')
		print(*l[i])
	elif s[-2] != s[-1]:
		i = head.index(s[-1])
		print(s[0], end=' ')
		print(*l[i])


import math
import sys
input = sys.stdin.readline
import heapq

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = int(input())
	ans = []
	datas = []
	nota = {}
	for i in range(n):
		datas.append(inlt())
	for i in range(n - 1):
		data = {}
		for j in range(n):
			if j in nota:
				continue
			if datas[j][i] in data:
				data[datas[j][i]][0] += 1
			else:
				data[datas[j][i]] = [1, j]
		kons = list(data.keys())
		if data[kons[0]][0] == 1 and data[kons[1]][0] == 1:
			notar = list(nota.keys())[0]
			ans += [datas[notar][-2], datas[notar][-1]]
			continue
		for k in data:
			if data[k][0] > 1:
				ans.append(k)
			else:
				nota[data[k][1]] = k
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	i = 2
	v1 = l1[0]
	v2 = l2[0]
	f = 0
	if v1 == v2:
		f = 1
	f1 = 0
	while n - i:
		l = list(map(int, input().split()))
		if f1 == 0:
			if f == 1:
				if l[0] != v1:
					r = [v1] + l
					f1 = 1
			else:
				if l[0] != v1:
					r = [l[0]] + l1
				else:
					r = [l[0]] + l2
				f1 = 1
		i += 1
	print(*r)


t = int(input())
for _ in range(t):
	n = int(input())
	li = []
	ans_li = []
	for _ in range(n):
		arr = list(map(int, input().split()))
		li.append(arr)
	li_sorted = sorted(li, key=lambda x: x[0])
	if li_sorted[0][0] == li_sorted[1][0] and li_sorted[0][0] != li_sorted[-1][0]:
		ans_li.append(li_sorted[0][0])
		ans_li.append(li_sorted[-1])
	else:
		ans_li.append(li_sorted[-1][0])
		ans_li.append(li_sorted[0])
	print(ans_li[0], *ans_li[1], end=' ')
	print()


from collections import defaultdict
t = int(input())
res = []
for _ in range(t):
	n = int(input())
	seq = []
	real = []
	freq = defaultdict(int)
	for i in range(n):
		a = list(map(int, input().split()))
		freq[a[0]] += 1
		seq.append(a)
	vals = sorted(freq.items(), key=lambda kv: kv[1])
	real.append(vals[1][0])
	real.append(vals[0][0])
	for j in range(1, n - 1):
		for i in range(n):
			if seq[i][j] not in real:
				real.append(seq[i][j])
				break
	res.append(real)
for i in res:
	print(*i)


t = int(input())
while t > 0:
	per = []
	first = []
	n = int(input())
	for i in range(n):
		tmp = list(map(int, input().split()))
		first.append(tmp[0])
		per.append(tmp)
	first2 = first.copy()
	first2.sort()
	if first2[0] != first2[1]:
		x = first2[1]
		ind = first.index(first2[0])
	else:
		x = first2[0]
		ind = first.index(first2[-1])
	first2 = []
	print(x, *per[ind])
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	if l1[0] == l2[0]:
		for i in range(n - 2):
			l = list(map(int, input().split()))
			if l[0] != l1[0]:
				print(l1[0], end=' ')
				for j in range(n - 1):
					if j == n - 2:
						print(l[j])
					else:
						print(l[j], end=' ')
	else:
		l = list(map(int, input().split()))
		if l[0] == l1[0]:
			print(l1[0], end=' ')
			for j in range(n - 1):
				if j == n - 2:
					print(l2[j])
				else:
					print(l2[j], end=' ')
		else:
			print(l[0], end=' ')
			for j in range(n - 1):
				if j == n - 2:
					print(l1[j])
				else:
					print(l1[j], end=' ')
		for k in range(n - 3):
			l = list(map(int, input().split()))


for t in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		p = [int(x) for x in input().rstrip().split()]
		l.append(p)
	l.sort()
	f = l[1][0]
	if f == l[0][0]:
		ans = l[-1]
		ans.insert(0, f)
	else:
		ans = l[0]
		ans.insert(0, f)
	for i in range(0, n - 1):
		print(ans[i], end=' ')
	print(ans[-1])


for _ in range(int(input())):
	lth = int(input())
	matrix = []
	for __ in range(lth):
		matrix.append(list(map(int, input().split())))
	if matrix[0][0] == matrix[1][0]:
		lhs = matrix[0][0]
	else:
		lhs = matrix[2][0]
	for i in range(lth):
		if matrix[i][0] != lhs:
			print(lhs, *matrix[i])


from math import gcd
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

def ye():
	print('Yes')

def no():
	print('NO')

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = list(map(int, input().split()))
	A = a[-1]
	B = b[-1]
	C = c[-1]
	S = 0
	s = []
	fl = 0
	if A == B:
		S = A
		if C != A:
			fl = 1
			s = c
	elif A == C:
		S = A
		fl = 1
		s = b
	else:
		S = B
		fl = 1
		s = a
	for i in range(3, n):
		now = list(map(int, input().split()))
		if fl:
			continue
		if now[-1] != S:
			s = now
			fl = 1
	for i in range(n - 1):
		print(s[i], end=' ')
	print(S)
	return
TT_T = int(input())
while TT_T:
	solve()
	TT_T -= 1


def one():
	n = int(input())
	t = []
	for i in range(n):
		t.append(list(map(int, input().split())))
	if t[0][0] != t[1][0] == t[2][0]:
		print(t[1][0], *t[0])
	else:
		x = t[0][0]
		for i in range(1, n):
			if t[i][0] != x:
				print(x, *t[i])
				return
t = int(input())
for i in range(t):
	one()


for t in range(int(input())):
	s = list()
	n = int(input())
	for i in range(n):
		s.append(list(map(int, input().split())))
	s.sort()
	if s[0][0] != s[1][0]:
		target = s[0]
	else:
		target = s[-1]
	ava = set(target)
	for i in range(1, n + 1):
		if i not in ava:
			print(*[i] + target)


t = int(input())

def solve():
	n = int(input())
	ps = []
	for _ in range(n):
		ps.append(list(map(int, input().split())))
	a = ps[0][0]
	b = ps[1][0]
	c = ps[2][0]
	if a == b:
		p0 = a
	elif a == c:
		p0 = a
	else:
		p0 = b
	ans = [p0]
	for i in range(n):
		if ps[i][0] != p0:
			ans.extend(ps[i])
	print(*ans)
for _ in range(t):
	solve()


def sol(mat, n):
	a = [0 for i in range(n)]
	if mat[0][0] == mat[1][0]:
		fe = mat[0][0]
	else:
		fe = mat[2][0]
	a[0] = fe
	r = 0
	for i in range(n):
		if mat[i][0] != fe:
			r = i
			break
	return [fe] + mat[r]
for _ in range(int(input())):
	n = int(input())
	mat = []
	for i in range(n):
		mat.append(list(map(int, input().split())))
	print(*sol(mat, n))


def solve():
	n = int(input())
	lis = list()
	for i in range(n):
		lis.append(list(map(int, input().split())))
	di = dict()
	for i in range(n):
		di[lis[i][0]] = di.get(lis[i][0], 0) + 1
	for i in range(n):
		if di[lis[i][0]] == 1:
			ans = lis[i]
			break
	for i in range(1, n + 1):
		if i not in ans:
			ans = [i] + ans
			print(*ans)
			break
for _ in range(int(input())):
	solve()


from math import *

def lstStrRd():
	return list(input())

def intRd():
	return int(input())

def lstRd():
	return list(map(int, input().split()))
for _ in range(intRd()):
	n = intRd()
	a = []
	s = []
	for i in range(n):
		a.append(lstRd())
	a = sorted(a)
	if a[0][0] == a[1][0]:
		print(a[0][0], *a[-1])
	else:
		print(a[-1][0], *a[0])


T = int(input())
while T:
	T -= 1
	n = int(input())
	first = -1
	flag = False
	temp = []
	tt = False
	q = [0] * 101
	for i in range(n):
		a = list(map(int, input().split()))
		if tt:
			continue
		temp.append(a)
		if flag:
			q = [0] * 101
			if temp[0][0] == temp[2][0]:
				print(temp[0][0], end=' ')
				for cc in temp[1]:
					print(cc, end=' ')
				print()
			else:
				print(temp[1][0], end=' ')
				for cc in temp[0]:
					print(cc, end=' ')
				print()
			tt = True
			continue
		if first == -1:
			first = a[0]
			q[a[0]] += 1
			continue
		elif first != a[0]:
			if q[first] > 1 and q[a[0]] == 0:
				print(first, end=' ')
				for cc in a:
					print(cc, end=' ')
				print()
				tt = True
				continue
			elif q[first] == 1 and q[a[0]] == 0:
				flag = True
				continue
		else:
			q[first] += 1
			continue