We guessed a permutation $p$ consisting of $n$ integers. The permutation of length $n$ is the array of length $n$ where each element from $1$ to $n$ appears exactly once. This permutation is a secret for you.

For each position $r$ from $2$ to $n$ we chose some other index $l$ ($l < r$) and gave you the segment $p_l, p_{l + 1}, \dots, p_r$ in sorted order (i.e. we rearranged the elements of this segment in a way that the elements of this segment are sorted). Thus, you are given exactly $n-1$ segments of the initial permutation but elements inside each segment are sorted. The segments are given to you in random order.

For example, if the secret permutation is $p=[3, 1, 4, 6, 2, 5]$ then the possible given set of segments can be:  $[2, 5, 6]$  $[4, 6]$  $[1, 3, 4]$  $[1, 3]$  $[1, 2, 4, 6]$ 

Your task is to find any suitable permutation (i.e. any permutation corresponding to the given input data). It is guaranteed that the input data corresponds to some permutation (i.e. such permutation exists).

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($2 \le n \le 200$) — the length of the permutation.

The next $n-1$ lines describe given segments.

The $i$-th line contains the description of the $i$-th segment. The line starts with the integer $k_i$ ($2 \le k_i \le n$) — the length of the $i$-th segment. Then $k_i$ integers follow. All integers in a line are distinct, sorted in ascending order, between $1$ and $n$, inclusive.

It is guaranteed that the required $p$ exists for each test case.

It is also guaranteed that the sum of $n$ over all test cases does not exceed $200$ ($\sum n \le 200$).


-----Output-----

For each test case, print the answer: $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ should be distinct) — any suitable permutation (i.e. any permutation corresponding to the test case input).


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

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

Difficulty: VERY_HARD
Tags: Constructive algorithms

Implementation

Greedy algorithms

Complete search

Data structures
Skill types: Complete search

Data structures

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def dfs(x, S):
	for i in range(len(S)):
		if x in S[i]:
			S[i].remove(x)
	LEN1 = 0
	for s in S:
		if len(s) == 1:
			LEN1 += 1
			ne = list(s)[0]
		if LEN1 == 2:
			return [-1]
	if LEN1 == 1:
		return [ne] + dfs(ne, S)
	else:
		return [-1]
import copy
t = int(input())
for tests in range(t):
	n = int(input())
	A = tuple((set(list(map(int, input().split()))[1:]) for i in range(n - 1)))
	for i in range(1, n + 1):
		ANS = [i] + dfs(i, copy.deepcopy(A))
		if -1 in ANS[:n]:
			continue
		else:
			USE = [0] * (n - 1)
			flag = 1
			for i in range(n - 1, 0, -1):
				SET = set()
				for j in range(i, -1, -1):
					SET.add(ANS[j])
					if SET in A:
						break
				else:
					flag = 0
					break
			if flag:
				print(*ANS[:n])
				break


import copy
t = int(input())

def fn(ivs, v, n):
	result = list()
	while len(result) < n - 1:
		w = None
		for iv in ivs:
			if v in iv:
				iv.remove(v)
				if len(iv) == 1:
					if w is None:
						w = iv.pop()
					else:
						return
		if w is None:
			return
		result.append(v)
		v = w
	result.append(v)
	return result

def check(res, sivs, n):
	if res is None:
		return False
	for i in range(1, n):
		good = False
		for j in range(i):
			if tuple(sorted(res[j:i + 1])) in sivs:
				good = True
		if not good:
			return False
	return True
for _ in range(t):
	n = int(input())
	ivs = list()
	for _ in range(n - 1):
		ivs.append(set(map(int, input().split(' ')[1:])))
	sivs = set()
	for iv in ivs:
		sivs.add(tuple(iv))
	for v in range(1, n + 1):
		res = fn(copy.deepcopy(ivs), v, n)
		if check(res, sivs, n):
			print(' '.join(map(str, res)))
			break


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def ok():
		if len(ans) < n:
			return False
		for (r, si) in enumerate(sii, 2):
			s = ss[si]
			cur = set(ans[r - len(s):r])
			if s != cur:
				return False
		return True
	for _ in range(II()):
		n = II()
		ee = [[n ** 2] * n for _ in range(n)]
		for ei in range(n):
			ee[ei][ei] = 0
		ss = [set(LI()[1:]) for _ in range(n - 1)]
		for a0 in range(1, n + 1):
			used = set([a0])
			ans = [a0]
			sii = []
			for _ in range(n - 1):
				nxt = []
				for (si, s) in enumerate(ss):
					cur = s - used
					if len(cur) == 1:
						for a in cur:
							nxt.append(a)
						sii.append(si)
				if len(nxt) != 1:
					break
				ans.append(nxt[0])
				used.add(nxt[0])
			if ok():
				break
		print(*ans)
main()


import copy
t = int(input())
for T in range(t):
	n = int(input())
	seg = [set(list(map(int, input().split()))[1:]) for i in range(n - 1)]
	p = [0] * n
	for first in range(1, n + 1):
		p[0] = first
		ok = True
		segt = copy.deepcopy(seg)
		for i in range(1, n):
			for s in segt:
				s.discard(p[i - 1])
			cnt1 = 0
			save = -1
			for s in segt:
				if len(s) == 1:
					cnt1 += 1
					save = s
			if cnt1 != 1:
				ok = False
				break
			p[i] = save.pop()
		if not ok:
			continue
		segt = copy.deepcopy(seg)
		for s in segt:
			yes = False
			start = False
			for i in range(n):
				if p[i] in s:
					if not start:
						start = True
					s.discard(p[i])
				elif start:
					break
				if start and len(s) == 0:
					yes = True
					break
			if not yes:
				ok = False
				break
		if not ok:
			continue
		for i in p:
			print(i, end=' ')
		print()
		break


import sys
import collections
import threading
import copy

def check(itr, sets):
	d = {}

	def dmap(x):
		return d[x]
	for i in range(len(itr)):
		d[itr[i]] = i
	for perm in sets:
		tmp = sorted(list(map(dmap, perm)))
		if len(tmp) != tmp[-1] - tmp[0] + 1:
			return False
	return True

def main():
	n = int(input())
	sets = []
	start = set()
	for _ in range(n - 1):
		(l, *tmp) = map(int, input().split())
		sets.append(set(tmp))
		if l == 2:
			start.add(tmp[0])
			start.add(tmp[1])
	ans = collections.deque()
	for i in start:
		permuts = copy.deepcopy(sets)
		next = i
		while len(ans) > 0:
			ans.pop()
		ans.append(next)
		while len(ans) < n:
			q = []
			for permut in permuts:
				if next in permut:
					permut.remove(next)
					if len(permut) == 1:
						q.append(permut)
			if len(q) != 1:
				break
			next = list(q[0])[0]
			ans.append(next)
		if len(ans) == n and check(ans, sets):
			print(*ans)
			return
	print('error')
	return
input = sys.stdin.readline
tnum = int(input())
for _ in range(tnum):
	main()


import io
import os
from collections import defaultdict
from copy import deepcopy

def solve(N, segments):

	def greedy(ans, memToSeg, first):
		while len(memToSeg) > 2:
			candidates = [k for (k, v) in memToSeg.items() if len(v) == 1 and k != first]
			if len(candidates) != 1:
				if len(candidates) == 0:
					assert first is not None
					return None
				assert len(candidates) == 2 and first is None
				for c in candidates:
					temp = greedy(deepcopy(ans), deepcopy(memToSeg), first=c)
					if temp is None:
						continue
					numToIndex = {x: i for (i, x) in enumerate(temp)}
					bad = False
					for segment in segments:
						mn = min((numToIndex[x] for x in segment))
						mx = max((numToIndex[x] for x in segment))
						if mx - mn + 1 != len(segment):
							bad = True
							break
					if not bad:
						return temp
				assert False
			else:
				assert len(candidates) == 1
				(k,) = candidates
				v = memToSeg[candidates[0]]
				assert len(v) == 1
				(index,) = v
				ans.append(k)
				for x in segments[index]:
					memToSeg[x].remove(index)
					if len(memToSeg[x]) == 0:
						assert x == k
						del memToSeg[x]
		firstTwo = []
		assert len(memToSeg) == 2
		for (k, v) in memToSeg.items():
			assert len(v) == 1
			firstTwo.append(k)
		if first is not None:
			assert first in firstTwo
			if firstTwo[0] == first:
				ans.append(firstTwo[1])
				ans.append(firstTwo[0])
			else:
				ans.append(firstTwo[0])
				ans.append(firstTwo[1])
		else:
			for segment in segments:
				if firstTwo[0] in segment and firstTwo[1] not in segment:
					ans.append(firstTwo[0])
					ans.append(firstTwo[1])
					break
				if firstTwo[1] in segment and firstTwo[0] not in segment:
					ans.append(firstTwo[1])
					ans.append(firstTwo[0])
					break
			else:
				ans.extend(firstTwo)
		return ans
	memToSeg = defaultdict(set)
	for (i, segment) in enumerate(segments):
		for x in segment:
			memToSeg[x].add(i)
	return ' '.join(map(str, reversed(greedy([], memToSeg, None))))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
for t in range(T):
	(N,) = [int(x) for x in input().split()]
	segments = []
	for i in range(N - 1):
		segment = [int(x) for x in input().split()]
		assert segment[0] == len(segment) - 1
		segments.append(segment[1:])
	ans = solve(N, segments)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	segs = [tuple(sorted((int(x) for x in input().split()[1:]))) for __ in range(n - 1)]
	segs_having = [[j for (j, seg) in enumerate(segs) if i in seg] for i in range(n + 1)]
	segs_set = set(segs)
	for first in range(1, n + 1):
		try:
			segs_copy = [set(seg) for seg in segs]
			ans = [first]
			while len(ans) < n:
				for seg in segs_having[ans[-1]]:
					segs_copy[seg].remove(ans[-1])
				ans.append(next(iter(next((seg for seg in segs_copy if len(seg) == 1)))))
			if all((any((tuple(sorted(ans[j:i])) in segs_set for j in range(0, i - 1))) for i in range(2, n + 1))):
				print(*ans)
				break
		except StopIteration:
			pass


import sys
from copy import copy, deepcopy
input = sys.stdin.readline
inf = 100000000000000000
mod = 998244353

def check():
	F = [0] * (n + 1)
	for i in range(len(ANS)):
		F[ANS[i]] = i
	isok = 1
	for a in A:
		l = inf
		r = 0
		for char in a:
			l = min(l, F[char])
			r = max(r, F[char])
		if r - l + 1 != len(a):
			isok = 0
			break
	return isok

def dfs(x, S):
	if x == n:
		global flag
		if check() == 1:
			if flag == 0:
				flag = 1
				print(*ANS)
	for s in S:
		new_member = 0
		for char in s:
			if char not in SET:
				if new_member == 0:
					new_member = char
				else:
					new_member = 0
					break
		if new_member != 0:
			S.remove(s)
			SET.add(new_member)
			ANS.append(new_member)
			dfs(x + 1, S)
for tests in range(int(input())):
	flag = 0
	n = int(input())
	A = list((list(map(int, input().split()))[1:] for i in range(n - 1)))
	for a in A:
		if len(a) == 2:
			ANS = [a[0], a[1]]
			S = deepcopy(A)
			S.remove(a)
			SET = set()
			SET.add(a[0])
			SET.add(a[1])
			dfs(2, S)
			S = deepcopy(A)
			S.remove(a)
			ANS = [a[1], a[0]]
			SET = set()
			SET.add(a[0])
			SET.add(a[1])
			dfs(2, S)


t = int(input())
for _ in range(t):
	n = int(input())
	ns = {}
	for _ in range(n - 1):
		(_, *p) = map(int, input().split())
		tp = tuple(p)
		for pp in p:
			ns.setdefault(pp, set()).add(tp)
	first = [(k, list(v)[0]) for (k, v) in ns.items() if len(v) == 1]
	found = False
	while not found:
		nns = {k: v.copy() for (k, v) in ns.items()}
		min_index = {}
		(cur, cur_tp) = first.pop()
		result = [cur]
		failed = False
		while len(nns) > 0 and (not failed):
			nxt = set()
			for k in cur_tp:
				mi = n - len(result) - len(cur_tp) + 1
				min_index[k] = max(min_index.get(k, 0), mi)
				nsk = nns[k]
				nsk.remove(cur_tp)
				if k == cur:
					nns.pop(k)
				elif len(nsk) == 1:
					nxt.add(k)
			if len(nns) == len(nxt) or len(nns) == 1:
				break
			if len(nxt) == 0:
				failed = True
			else:
				mmi = -1
				for nx in nxt:
					if min_index[nx] > mmi:
						mmi = min_index[nx]
						cur = nx
				cur_tp = list(nns[cur])[0]
				result.append(cur)
		if not failed:
			found = True
			if len(nns) == 1:
				result.append(nns.popitem()[0])
			else:
				(a1, a2) = nns.keys()
				if min_index[a1] == 1:
					result.extend((a1, a2))
				else:
					result.extend((a2, a1))
			print(' '.join(map(str, reversed(result))))


for _ in range(int(input())):
	n = int(input())
	segs = [tuple(sorted((int(x) for x in input().split()[1:]))) for __ in range(n - 1)]
	segs_set = set(segs)
	segs_having = [[j for (j, seg) in enumerate(segs) if i in seg] for i in range(n + 1)]
	unsorted = list(range(1, n + 1))
	ans = []

	def rb(avoid=0):
		if len(unsorted) > 1:
			candidate_lasts = [i for i in unsorted if len(segs_having[i]) == 1 and i != avoid]
			for last in candidate_lasts:
				seg_to_remove = segs_having[last][0]
				for ii in segs[seg_to_remove]:
					segs_having[ii].remove(seg_to_remove)
				unsorted.remove(last)
				ans.insert(0, last)
				if rb(avoid=next((i for i in candidate_lasts if i != last), avoid)):
					return True
				ans.pop(0)
				unsorted.append(last)
				for ii in segs[seg_to_remove]:
					segs_having[ii].append(seg_to_remove)
			return False
		else:
			ans.insert(0, unsorted[0])
			valid = all((any((tuple(sorted(ans[j:i])) in segs_set for j in range(0, i - 1))) for i in range(2, n + 1)))
			if not valid:
				ans.pop(0)
			return valid
	rb()
	print(*ans)


from collections import defaultdict as dd
from pprint import pprint as pp

def solve():
	n = int(input())
	seqs = []
	d = dd(list)
	for _ in range(n - 1):
		seqs.append(list(map(int, input().split()[1:])))
	for seq in seqs:
		for i in range(len(seq)):
			s = ' '.join((str(x) for (j, x) in enumerate(seq) if j != i))
			d[s].append(seq[i])
	for st in range(1, n + 1):
		seq = [st]
		seq_set = {st}
		for _ in range(n - 1):
			found = False
			for l in range(len(seq)):
				k = ' '.join((str(x) for x in sorted(seq[-(l + 1):])))
				if k in d:
					for j in d[k]:
						if j not in seq_set:
							seq.append(j)
							seq_set.add(j)
							found = True
							break
				if found:
					break
			if not found:
				break
		if len(seq) == n:
			print(' '.join((str(x) for x in seq)))
			break
for _ in range(int(input())):
	solve()


from collections import Counter
from itertools import chain

def dfs(n, r, hint_sets, count, removed, result):
	if len(result) == n - 1:
		last = (set(range(1, n + 1)) - set(result)).pop()
		result.append(last)
		return True
	(i, including_r) = (0, None)
	for (i, including_r) in enumerate(hint_sets):
		if i in removed:
			continue
		if r in including_r:
			break
	removed.add(i)
	next_r = []
	for q in including_r:
		count[q] -= 1
		if count[q] == 1:
			next_r.append(q)
	if not next_r:
		return False
	if len(next_r) == 2:
		nr = -1
		(can1, can2) = next_r
		for h in hint_sets:
			if can1 in h and can2 not in h and (not h.isdisjoint(result)):
				nr = can1
				break
			if can1 not in h and can2 in h and (not h.isdisjoint(result)):
				nr = can2
				break
		if nr == -1:
			nr = can1
	else:
		nr = next_r[0]
	result.append(nr)
	res = dfs(n, nr, hint_sets, count, removed, result)
	if res:
		return True
	result.pop()
	for q in including_r:
		count[q] += 1
	return False
t = int(input())
buf = []
for l in range(t):
	n = int(input())
	hints = []
	for _ in range(n - 1):
		(k, *ppp) = list(map(int, input().split()))
		hints.append(ppp)
	count = Counter(chain.from_iterable(hints))
	most_common = count.most_common()
	hint_sets = list(map(set, hints))
	r = most_common[-1][0]
	result = [r]
	if dfs(n, r, hint_sets, dict(count), set(), result):
		buf.append(' '.join(map(str, result[::-1])))
		continue
	r = most_common[-2][0]
	result = [r]
	assert dfs(n, r, hint_sets, dict(count), set(), result)
	buf.append(' '.join(map(str, result[::-1])))
print('\n'.join(map(str, buf)))


from sys import stdin, gettrace
from copy import deepcopy
if not gettrace():

	def input():
		return next(stdin)[:-1]

def main():

	def solve():
		n = int(input())
		segs = []
		occur = [set() for _ in range(n + 1)]
		for j in range(n - 1):
			seg = frozenset((int(a) for a in input().split()[1:]))
			for i in seg:
				occur[i].add(seg)
		pl = []
		for i in range(1, n + 1):
			if len(occur[i]) == 1:
				pl.append(i)
		for p in pl:
			occurc = deepcopy(occur)
			res = [0] * n
			pos = n - 1
			sum = n * (n + 1) // 2
			while True:
				sum -= p
				res[pos] = p
				if pos == 1:
					res[0] = sum
					print(' '.join(map(str, res)))
					return
				np = []
				for seg in occurc[p]:
					for i in seg:
						if i == p:
							continue
						occurc[i].remove(seg)
						if len(occurc[i]) == 1:
							np.append(i)
				occurc[p].remove(seg)
				if len(np) == 1:
					p = np[0]
				elif len(np) == 2:
					if len(occur[np[0]]) > len(occur[np[1]]):
						p = np[0]
					else:
						p = np[1]
				else:
					break
				pos -= 1
	q = int(input())
	for _ in range(q):
		solve()
main()