Johnny, like every mathematician, has his favorite sequence of distinct natural numbers.  Let’s call this sequence $\mbox{M}$. Johnny was very bored, so he wrote down $N$ copies of the sequence $\mbox{M}$ in his big notebook. One day, when Johnny was out, his little sister Mary erased some numbers(possibly zero) from every copy of $\mbox{M}$ and then threw the notebook out onto the street. You just found it. Can you reconstruct the sequence? 

In the input there are $N$ sequences of natural numbers representing the $N$ copies of the sequence $\mbox{M}$ after Mary’s prank. In each of them all numbers are distinct. Your task is to construct the shortest sequence $\mbox{S}$ that might have been the original $\mbox{M}$. If there are many such sequences, return the lexicographically smallest one. It is guaranteed that such a sequence exists.

Note 

Sequence $A[1\ldots n]$ is lexicographically less than sequence $B[1\ldots n]$ if and only if there exists $1\leq i\leq n$ such that for all $1\leq j\lt i,A[j]=B[j]\:\textit{and}\:\:A[i]\lt B[i]$.

Input Format

In the first line, there is one number $N$ denoting the number of copies of $\mbox{M}$. 

This is followed by $\mbox{K}$ 

and in next line a sequence of length $\mbox{K}$ representing one of sequences after Mary's prank. All numbers are separated by a single space.  

Constraints 

$1\leq N\leq10^3$ 

$2\leq K\leq10^3$ 

All values in one sequence are distinct numbers in range $[1,10^{6}]$.

Output Format

In one line, write the space-separated sequence $\mbox{S}$ - the shortest sequence that might have been the original $\mbox{M}$. If there are many such sequences, return the lexicographically smallest one.

Sample Input
2
2
1 3
3
2 3 4

Sample Output
 1 2 3 4

Explanation

You have 2 copies of the sequence with some missing numbers: $[1,3]$ and $[2,3,4]$. There are two candidates for the original sequence $M:[1,2,3,4]\ \text{and}\ [2,1,3,4]$, where the first one is lexicographically least.

Source: hackerrank | Difficulty: HARD
Tags: Graph algorithms


Solutions:
from collections import defaultdict
n = int(input())
before_maps = defaultdict(set)
after_maps = defaultdict(set)
for _ in range(n):
	k = int(input())
	sequence = map(int, input().split())
	prev = 0
	for num in sequence:
		if prev:
			before_maps[num].add(prev)
		after_maps[prev].add(num)
		prev = num
m = []
actives = set((active for active in after_maps[0] if not before_maps[active]))
while actives:
	next_step = sorted(actives)[0]
	actives.remove(next_step)
	for step in after_maps[next_step]:
		before_maps[step].remove(next_step)
	actives.update((active for active in after_maps[next_step] if not before_maps[active]))
	m.append(next_step)
print(' '.join(map(str, m)))


from queue import PriorityQueue

def lextoposort(g):
	G = g.copy()
	I = dict()
	for (k, es) in G.items():
		for e in es:
			if e in I:
				I[e].add(k)
			else:
				I[e] = set([k])
	L = []
	S = PriorityQueue()
	for k in G.keys():
		if not k in I:
			S.put(k)
	while not S.empty():
		n = S.get()
		L.append(n)
		for m in G.get(n, []).copy():
			G[n].remove(m)
			I[m].remove(n)
			if not I[m]:
				S.put(m)
	return L
m = int(input())
g = dict()
for _ in range(m):
	k = int(input())
	s = list(map(int, input().split()))
	for i in range(k - 1):
		if s[i] in g:
			g[s[i]].add(s[i + 1])
		else:
			g[s[i]] = set([s[i + 1]])
print(*lextoposort(g))


import heapq
copy_count = int(input())
copies = []
for _ in range(copy_count):
	_ = int(input())
	copies.append([int(i) for i in input().split()])

class Node:
	id = 0
	constrained_by = set()
	constrains = set()

	def __init__(self, id):
		self.id = id
		self.constrained_by = set()
		self.constrains = set()

	def __str__(self):
		string = '[id=' + str(self.id) + ' from={'
		for i in self.constrained_by:
			string += str(i) + ','
		string += '} to={'
		for i in self.constrains:
			string += str(i) + ','
		string += '}'
		return string
nodes = [None for _ in range(1000000)]
max_id = 0
for copy in copies:
	previous_i = 0
	for i in copy:
		if i > max_id:
			max_id = i
		if nodes[i] == None:
			nodes[i] = Node(i)
		if previous_i != 0:
			nodes[i].constrained_by.add(previous_i)
			nodes[previous_i].constrains.add(i)
		previous_i = i
min_no_null = 0

def find_non_constrained_lex_min():
	global min_no_null
	i = min_no_null
	while i <= max_id:
		if nodes[i] != None:
			break
		else:
			i += 1
	min_no_null = i
	while i <= max_id:
		if nodes[i] != None and len(nodes[i].constrained_by) == 0:
			return i
		else:
			i += 1
no_constraint_node_heap = []
for i in range(1, max_id + 1):
	if nodes[i] != None and len(nodes[i].constrained_by) == 0:
		heapq.heappush(no_constraint_node_heap, i)
result = []
for i in range(1, max_id + 1):
	if len(no_constraint_node_heap) == 0:
		break
	min_id = heapq.heappop(no_constraint_node_heap)
	result.append(min_id)
	for j in nodes[min_id].constrains:
		nodes[j].constrained_by.remove(min_id)
		if len(nodes[j].constrained_by) == 0:
			heapq.heappush(no_constraint_node_heap, j)
string = ''
for i in result:
	string += str(i) + ' '
print(string)


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


class Digraph:

	def __init__(self):
		self.allno = set()
		self.pred = dict()
		self.succ = dict()
		self.label = dict()
		self.curr_label = 0
		self.candidates_available = False
		self.candidates = list()

	def _add_(self, father, son):
		if son in self.pred:
			self.pred[son].add(father)
		else:
			self.pred[son] = {father}
		if father in self.succ:
			self.succ[father].add(son)
		else:
			self.succ[father] = {son}

	def no_pred(self):
		op = set(self.allno)
		op.difference_update(set(self.pred.keys()))
		return op

	def _remove_(self, no):
		self.allno.remove(no)
		if no not in self.succ:
			return
		for successor in self.succ[no]:
			self.pred[successor].remove(no)
			if len(self.pred[successor]) == 0:
				self.pred.pop(successor)
				self.candidates.append(successor)
		self.succ.pop(no)

	def finalize(self, no):
		self._remove_(no)
		self.label[self.curr_label] = no
		self.curr_label += 1

	def add_seq(self, seq):
		self.allno.update(set(seq))
		for i in range(1, len(seq)):
			self._add_(seq[i - 1], seq[i])

	def get_min_seq(self):
		self.schedule()
		op = list()
		labels = sorted(list(self.label.keys()))
		for i in labels:
			op.append(self.label[i])
		return op

	def schedule(self):
		if len(self.allno) > 0:
			pending = True
		while pending:
			pending = False
			if not self.candidates_available:
				self.candidates = list(self.no_pred())
				self.candidates_available = True
			self.candidates.sort()
			candidate = self.candidates[0]
			self.finalize(candidate)
			self.candidates.remove(candidate)
			if len(self.allno) > 0:
				pending = True
d = Digraph()
n = int(input().strip())
for i in range(n):
	k = int(input().strip())
	ip = [int(x) for x in input().strip().split(' ')]
	assert k == len(ip)
	d.add_seq(ip)
seq = d.get_min_seq()
print(' '.join([str(x) for x in seq]))


from collections import defaultdict
n_sequences = int(input())
nodes = set()
parents_by_node = defaultdict(set)
children_by_node = defaultdict(set)

def pairs(l):
	return zip(l, l[1:])
for _ in range(n_sequences):
	length = int(input())
	values = [int(x) for x in input().split()]
	nodes.update(values)
	for (p, c) in pairs(values):
		parents_by_node[c].add(p)
		children_by_node[p].add(c)
answer = []
parentless_nodes = [n for n in nodes if not parents_by_node[n]]
while parentless_nodes:
	parentless_nodes.sort()
	n = parentless_nodes.pop(0)
	answer.append(n)
	for c in children_by_node[n]:
		parents = parents_by_node[c]
		parents.discard(n)
		if not parents:
			parentless_nodes.append(c)
print(' '.join((str(x) for x in answer)))


import heapq

def push(pq, item):
	heapq.heappush(pq, [item['v'], item])

def pop(pq):
	return heapq.heappop(pq)[1]
N = int(input())
nodes = {}
for _ in range(N):
	K = int(input())
	arr = list(map(int, input().split(' ')))
	prev = None
	for i in arr:
		curr = nodes.setdefault(i, {'c': [], 'v': i})
		if prev != None:
			prev['c'].append(curr)
			curr['p'] = curr.get('p', 0) + 1
		prev = curr
cand = []
for n in nodes.values():
	if n.get('p', 0) == 0:
		push(cand, n)
res = []
while len(cand) > 0:
	curr = pop(cand)
	if curr['v'] not in nodes:
		continue
	res.append(curr['v'])
	for ch in curr['c']:
		ch['p'] = ch.get('p', 0) - 1
		if ch['p'] <= 0:
			push(cand, ch)
	nodes.pop(curr['v'], None)
print(' '.join(map(str, res)))


from collections import defaultdict
from heapq import heappush, heappop

class Graph:

	def __init__(self):
		self.nodes = set()
		self.origins = set()
		self.targets = set()
		self.edges = defaultdict(set)
		self.incomings = defaultdict(set)

	def join(self, a, b):
		self.nodes.update([a, b])
		self.origins.add(a)
		self.targets.add(b)
		self.edges[a].add(b)
		self.incomings[b].add(a)

	def disc(self, a, b):
		self.edges[a].remove(b)
		self.incomings[b].remove(a)

	def inc_count(self, a):
		return len(self.incomings[a])

	def children(self, a):
		assert a in self.nodes
		return self.edges[a]

	def parents(self):
		a = list(self.origins - self.targets)
		a.sort()
		return a
G = Graph()
N = int(input())
for _ in range(N):
	M = int(input())
	A = [int(c) for c in input().strip().split()]
	for i in range(1, len(A)):
		a = A[i - 1]
		b = A[i]
		G.join(a, b)
h = []
final = []
visited = set()
for c in G.parents():
	heappush(h, c)
while len(h) > 0:
	n = heappop(h)
	final.append(n)
	for c in list(G.children(n)):
		G.disc(n, c)
		if G.inc_count(c) == 0:
			heappush(h, c)
print(' '.join([str(i) for i in final]))


import sys
from heapq import heapify, heappush, heappop
line_count = 0
(sources, non_sources, edges, rev_edges) = (set(), set(), {}, {})
for line in sys.stdin.readlines():
	line_count += 1
	if line_count == 1 or line_count % 2 == 0:
		continue
	if line[-1] == '\n':
		line = line[:-1]
	seq = list(map(int, line.split(' ')))
	sources.add(seq[0])
	for i in range(1, len(seq)):
		if seq[i - 1] not in edges:
			edges[seq[i - 1]] = set()
		if seq[i] not in rev_edges:
			rev_edges[seq[i]] = set()
		edges[seq[i - 1]].add(seq[i])
		rev_edges[seq[i]].add(seq[i - 1])
		non_sources.add(seq[i])
sources = sources - non_sources
(top, visited) = ([], sources)
fringe = list(sources)
heapify(fringe)
while len(fringe) > 0:
	n = heappop(fringe)
	top.append(n)
	if n not in edges:
		continue
	for m in edges[n]:
		rev_edges[m].remove(n)
		if len(rev_edges[m]) == 0:
			heappush(fringe, m)
print(' '.join(map(str, top)))


import heapq
G = {}
pq = []
N = int(input())

class Node:
	parents = None
	children = None

	def __init__(self):
		self.parents = []
		self.children = []

	def getParentsSize(self):
		return len(self.parents)

	def getChildrenSize(self):
		return len(self.children)

def kahns(g, s):
	L = []
	while s:
		n = heapq.heappop(s)
		L.append(n)
		while g[n].children:
			m = g[n].children.pop(0)
			g[m].parents.remove(n)
			if g[m].getParentsSize() == 0:
				heapq.heappush(pq, m)
	return L
for i in range(N):
	K = int(input())
	arr = [int(x) for x in input().split()]
	if arr[0] not in G:
		G[arr[0]] = Node()
	for j in range(1, K):
		if arr[j] not in G:
			G[arr[j]] = Node()
		G[arr[j - 1]].children.append(arr[j])
		G[arr[j]].parents.append(arr[j - 1])
for i in G:
	if G[i].getParentsSize() == 0:
		heapq.heappush(pq, i)
l = kahns(G, pq)
print(' '.join((str(x) for x in l)))


class Edge:

	def __init__(self, toNode, weight):
		self.toNode = toNode
		self.weight = weight

	def __repr__(self):
		return 'to ' + str(self.toNode) + ' with weight ' + str(self.weight)

class Graph:

	def __init__(self, N):
		self.__adjacencyLists = [[] for _ in range(N)]

	def display(self):
		print('==== GRAPH DISPLAY ====')
		for i in range(len(self.__adjacencyLists)):
			print(str(i) + ':')
			for elt in self.__adjacencyLists[i]:
				print('-', str(elt))
		print('==== END OF DISPLAY ====')

	def addEdge(self, node1, node2, weight=1):
		self.__adjacencyLists[node1].append(Edge(node2, weight))

	def addNode(self, node):
		N = len(self.__adjacencyLists)
		for i in range(N, node):
			self.__adjacencyLists.append([])

	def numVertices(self):
		return len(self.__adjacencyLists)

	def topologicalSort(self, order_func):
		N = self.numVertices()
		incomingEdges = [0 for _ in range(N)]
		topologicalOrder = []
		activeNodes = []
		for i in range(N):
			for edge in self.__adjacencyLists[i]:
				incomingEdges[edge.toNode] += 1
		for i in range(N):
			if incomingEdges[i] == 0:
				activeNodes.append(i)
		while activeNodes:
			activeNodes.sort(key=order_func, reverse=True)
			n = activeNodes.pop()
			for edge in self.__adjacencyLists[n]:
				incomingEdges[edge.toNode] -= 1
				if incomingEdges[edge.toNode] == 0:
					activeNodes.append(edge.toNode)
			topologicalOrder.append(n)
		return topologicalOrder
g = Graph(1)
node_to_input = dict()
input_to_node = dict()
for _ in range(int(input().strip())):
	dummy = input()
	sequence = [int(x) for x in input().strip().split()]
	for elt in sequence:
		if elt not in input_to_node.keys():
			v = len(node_to_input)
			input_to_node[elt] = v
			node_to_input[v] = elt
	maxNode = len(node_to_input)
	if g.numVertices() <= maxNode:
		g.addNode(maxNode)
	for i in range(len(sequence) - 1):
		g.addEdge(input_to_node[sequence[i]], input_to_node[sequence[i + 1]])

def order_func(n):
	return node_to_input[n]
topSort = g.topologicalSort(order_func)
print(' '.join([str(node_to_input[x]) for x in topSort]))


import sys
from collections import OrderedDict, defaultdict

class heapq(object):

	@staticmethod
	def _bubbleup(h, pos):
		while pos > 0:
			parent_idx = (pos - 1) // 2
			if h[pos] >= h[parent_idx]:
				return
			(h[pos], h[parent_idx]) = (h[parent_idx], h[pos])
			pos = parent_idx
		return

	@staticmethod
	def _bubbledown(h, pos):
		while 2 * pos + 1 < len(h):
			(kid_idx1, kid_idx2) = (2 * pos + 1, 2 * pos + 2)
			smaller_kid_idx = kid_idx2 if kid_idx2 < len(h) and h[kid_idx2] < h[kid_idx1] else kid_idx1
			if h[pos] <= h[smaller_kid_idx]:
				return
			(h[pos], h[smaller_kid_idx]) = (h[smaller_kid_idx], h[pos])
			pos = smaller_kid_idx
		return

	@staticmethod
	def heappush(h, el):
		h.append(el)
		heapq._bubbleup(h, len(h) - 1)

	@staticmethod
	def heappop(h):
		(h[0], h[-1]) = (h[-1], h[0])
		v = h.pop()
		heapq._bubbledown(h, 0)
		return v

	@staticmethod
	def heapsort(h):
		(result, heap) = ([], [])
		while h:
			heapq.heappush(heap, h.pop())
		for x in heap:
			h.append(x)
		while heap:
			x = heapq.heappop(heap)
			result.append(x)
		return result

class Graph(object):

	def __init__(self, lst_of_vertices, adj_list):
		self.v = lst_of_vertices
		self.adj_list = adj_list

	def map_vertex_onto_in_edges(self):
		d2 = defaultdict(set)
		for v in self.v:
			for e in self.adj_list[v]:
				d2[e].add(v)
		in_keys = sorted(self.v, key=lambda v: (len(d2[v]), v), reverse=False)
		return OrderedDict([(k, d2[k]) for k in in_keys])

	def initial_fill_0_indegree_heap(self, indegree_d):
		heap_0_indegree = []
		for (k, v) in indegree_d.items():
			if not v:
				heapq.heappush(heap_0_indegree, k)
		return heap_0_indegree

	def lex_top_sort(self):
		inedgest_v_dict = self.map_vertex_onto_in_edges()
		heap_0_indegree = self.initial_fill_0_indegree_heap(inedgest_v_dict)
		lex_topological_order = []
		while inedgest_v_dict:
			min_0_indegree_k = heapq.heappop(heap_0_indegree)
			lex_topological_order.append(min_0_indegree_k)
			del inedgest_v_dict[min_0_indegree_k]
			for j in self.adj_list[min_0_indegree_k]:
				inedgest_v_dict[j].remove(min_0_indegree_k)
				if not inedgest_v_dict[j]:
					heapq.heappush(heap_0_indegree, j)
		return lex_topological_order

def enter_data():
	screened_lists = []
	n = int(input().strip())
	for i in range(n):
		k = int(input().strip())
		arr = [int(a) for a in input().strip().split(' ')]
		screened_lists.append(arr)
	return screened_lists

def create_unsorted_adj_list(screened_lists):
	adj_list = defaultdict(set)
	for seq in screened_lists:
		for (i, s) in enumerate(seq[:-1]):
			adj_list[s].add(seq[i + 1])
		adj_list[seq[-1]].add(None)
		adj_list[seq[-1]].remove(None)
	return adj_list

def create_sorted_adj_list(adj_list):
	sorted_adj_list = OrderedDict()
	keys = sorted(adj_list.keys(), reverse=True)
	for k in keys:
		v = adj_list[k]
		v2 = sorted(list(v), reverse=True)
		sorted_adj_list[k] = v2
	return sorted_adj_list

def make_graph(sorted_adj_list):
	adj_list = sorted_adj_list
	g = Graph(lst_of_vertices=adj_list.keys(), adj_list=adj_list)
	return g

def create_graph(screened_lists):
	adj_list = create_unsorted_adj_list(screened_lists)
	sorted_adj_list = create_sorted_adj_list(adj_list)
	return make_graph(sorted_adj_list)

def restore_possible_sequence(screened_lists):
	g = create_graph(screened_lists)
	order = ' '.join([str(x) for x in g.lex_top_sort()])
	return order
screened_lists = enter_data()
order = restore_possible_sequence(screened_lists)
print(order)


from collections import defaultdict
import queue

def getSmallestTopOrder(inEdges, outEdges, vertices):
	topOrder = []
	noIncNodes = queue.PriorityQueue()
	for i in vertices:
		if i not in inEdges.keys():
			noIncNodes.put(i)
	while not noIncNodes.empty():
		v = noIncNodes.get()
		topOrder.append(v)
		vOutgoing = outEdges.get(v, None)
		if vOutgoing != None:
			for w in vOutgoing:
				inEdges[w].remove(v)
			for w in vOutgoing:
				inSet = inEdges.get(w, None)
				if inSet != None and len(inSet) == 0:
					noIncNodes.put(w)
					inEdges.pop(w, None)
		outEdges.pop(v, None)
	output = ''
	for v in topOrder:
		output += '{} '.format(v)
	return output
nCopies = int(input())
vertices = set()
inEdges = defaultdict(set)
outEdges = defaultdict(set)
for copyOfM in range(nCopies):
	k = int(input())
	seq = [int(i) for i in input().split(' ')]
	for i in range(len(seq) - 1):
		outEdges[seq[i]].add(seq[i + 1])
		inEdges[seq[i + 1]].add(seq[i])
		vertices.add(seq[i])
	if len(seq) > 0:
		vertices.add(seq[-1])
print(getSmallestTopOrder(inEdges, outEdges, vertices))


def parent(i):
	return (i - 1) // 2

def left(i):
	return 2 * i + 1

def right(i):
	return 2 * i + 2

def heapifyUp(H, p):
	while p > 0 and H[parent(p)] > H[p]:
		(H[parent(p)], H[p]) = (H[p], H[parent(p)])
		p = parent(p)

def heapifyDown(H, p):
	while left(p) < len(H):
		m = 0
		if right(p) > len(H) - 1:
			m = left(p)
		elif H[left(p)] < H[right(p)]:
			m = left(p)
		else:
			m = right(p)
		if H[p] <= H[m]:
			return
		(H[p], H[m]) = (H[m], H[p])
		p = m

def pop(H):
	m = H[0]
	H[0] = H[len(H) - 1]
	del H[len(H) - 1]
	heapifyDown(H, 0)
	return m

def add(H, x):
	H.append(x)
	heapifyUp(H, len(H) - 1)

def sol(seqs):
	adj = {}
	pre = {}
	deg0 = []
	for l in seqs:
		if not l[0] in deg0:
			deg0.append(l[0])
	for l in seqs:
		for i in range(len(l) - 1):
			if l[i + 1] in deg0:
				deg0.remove(l[i + 1])
			if not l[i] in adj.keys():
				adj[l[i]] = []
			if not l[i + 1] in pre.keys():
				pre[l[i + 1]] = []
			if not l[i + 1] in adj[l[i]]:
				adj[l[i]].append(l[i + 1])
				pre[l[i + 1]].append(l[i])
		if not l[len(l) - 1] in adj.keys():
			adj[l[len(l) - 1]] = []
	H = []
	for i in deg0:
		add(H, i)
	res = []
	while len(H) > 0:
		cur = pop(H)
		res.append(cur)
		for i in adj[cur]:
			if cur in pre[i]:
				pre[i].remove(cur)
				if len(pre[i]) == 0:
					add(H, i)
	return res
n = int(input())
seqs = [[] for _ in range(n)]
for i in range(n):
	k = int(input())
	seqs[i] = list(map(int, input().split(' ')))
print(' '.join((str(i) for i in sol(seqs))))


class MinHeap:

	def __init__(self, size):
		self.A = []
		self.A.append(None)
		self.A.append(None)
		for i in range(size):
			self.A.append(None)
		self.n = 0

	def get_min(self):
		return self.A[1]

	def insert(self, t):
		self.n += 1
		self.A[self.n] = t
		self.heapify_up(self.n)

	def delete_min(self):
		e = self.A[1]
		self.A[1] = self.A[self.n]
		self.A[self.n] = None
		self.n -= 1
		self.heapify_down(1)
		return e

	def heapify_up(self, i):
		while i > 1 and self.A[self.parent(i)] > self.A[i]:
			(self.A[i], self.A[self.parent(i)]) = (self.A[self.parent(i)], self.A[i])
			i = self.parent(i)

	def heapify_down(self, i):
		while self.left(i) <= self.n:
			if self.right(i) > self.n:
				m = self.left(i)
			elif self.A[self.left(i)] < self.A[self.right(i)]:
				m = self.left(i)
			else:
				m = self.right(i)
			if self.A[i] <= self.A[m]:
				return
			(self.A[i], self.A[m]) = (self.A[m], self.A[i])
			i = m

	@staticmethod
	def parent(i):
		return i // 2

	@staticmethod
	def left(i):
		return 2 * i

	@staticmethod
	def right(i):
		return 2 * i + 1

	def __str__(self):
		return str(self.A)

def mathishard(B):
	L = []
	outgoing = {}
	incoming = {}
	length = 0
	for lists in B:
		length += len(lists)
		for elem in lists:
			if elem not in outgoing.keys():
				outgoing[elem] = []
			if elem not in incoming.keys():
				incoming[elem] = 0
		if len(lists) >= 2:
			for i in range(len(lists) - 1):
				outgoing[lists[i]].append(lists[i + 1])
				incoming[lists[i + 1]] += 1
	S = MinHeap(length)
	for i in incoming.keys():
		if incoming[i] == 0:
			S.insert(i)
	while S.get_min() != None:
		n = S.delete_min()
		L.append(n)
		u = outgoing[n]
		for following in outgoing[n]:
			u = u[1:]
			incoming[following] -= 1
			if incoming[following] == 0:
				S.insert(following)
		outgoing[n] = u
	return L
n = int(input())
seqs = [[] for _ in range(n)]
for i in range(n):
	k = int(input())
	seqs[i] = list(map(int, input().split(' ')))
print(' '.join((str(i) for i in mathishard(seqs))))


class Node:

	def __init__(self, value):
		self.value = value
		self.parents = []
		self.children = []

class Graph:

	def __init__(self):
		self.vertices = {}
		self.heads = {}

	def addHead(self, value):
		if value in self.vertices.keys():
			return
		newNode = Node(value)
		self.vertices[value] = newNode
		self.heads[value] = newNode

	def addConnection(self, fromValue, toValue):
		if not fromValue in self.vertices.keys():
			return
		if not toValue in self.vertices.keys():
			self.vertices[toValue] = Node(toValue)
		self.vertices[fromValue].children += [toValue]
		self.vertices[toValue].parents += [fromValue]
		if toValue in self.heads.keys():
			self.heads.pop(toValue)

	def removeAndUpdateHead(self, headValue):
		if not headValue in self.heads:
			return
		newHeads = []
		for childValue in self.vertices[headValue].children:
			self.vertices[childValue].parents = arrayByRemovingOnce(self.vertices[childValue].parents, headValue)
			if len(self.vertices[childValue].parents) == 0:
				newHeads += [childValue]
		self.heads.pop(headValue)
		self.vertices.pop(headValue)
		for newValue in newHeads:
			if newValue not in self.heads.keys():
				self.heads[newValue] = self.vertices[newValue]

def arrayByRemovingOnce(A, value):
	pos = 0
	for i in range(len(A)):
		if A[i] == value:
			pos = i
			break
	return A[:pos] + A[pos + 1:]

def minimumInList(A):
	if len(A) == 0:
		return None
	mini = A[0]
	for i in A[1:]:
		if mini > i:
			mini = i
	return mini

def mathishard(B):
	graph = Graph()
	for sequence in B:
		if len(sequence) == 0:
			continuea
		possibleHead = sequence[0]
		graph.addHead(possibleHead)
		for nextIndex in range(len(sequence[1:])):
			nextIndex += 1
			lastIndex = nextIndex - 1
			graph.addConnection(sequence[lastIndex], sequence[nextIndex])
	finalList = []
	while len(graph.heads) > 0:
		nextItem = minimumInList(list(graph.heads.keys()))
		finalList += [nextItem]
		graph.removeAndUpdateHead(nextItem)
	return finalList
n = int(input())
seqs = [[] for _ in range(n)]
for i in range(n):
	k = int(input())
	seqs[i] = list(map(int, input().split(' ')))
print(' '.join((str(i) for i in mathishard(seqs))))


from collections import defaultdict
import bisect

class Graph:

	def __init__(self):
		self.graph = defaultdict(set)
		self.up = defaultdict(set)
		self.vertices = set()

	def addEdge(self, u, v):
		self.graph[u].add(v)
		self.up[v].add(u)
		self.vertices.add(u)
		self.vertices.add(v)

	def topologicalSort(self):
		L = []
		S = sorted(list(self.vertices - set.union(*[value for (key, value) in self.graph.items()])))
		while S:
			n = S.pop(0)
			L.append(n)
			for m in self.graph[n].copy():
				self.graph[n].discard(m)
				self.up[m].discard(n)
				if not self.up[m]:
					bisect.insort_left(S, m)
		return L
g = Graph()
N = int(input())
for i in range(N):
	K = int(input())
	m = input().strip().split(' ')
	for (index, node) in enumerate(m):
		if index != len(m) - 1:
			g.addEdge(int(node), int(m[index + 1]))
sort = g.topologicalSort()
print(' '.join([str(node) for node in sort]))


import sys
from bisect import insort
D = dict()
result = []
N = int(input().strip())
for _ in range(N):
	next(sys.stdin)
	tokens = [*map(int, input().split())]
	x = tokens[0]
	for y in tokens[1:]:
		try:
			unique = not D[x][1].__contains__(y)
			if unique:
				D[x][1].add(y)
		except KeyError:
			unique = True
			D[x] = [0, set({y})]
		if unique:
			try:
				D[y][0] += 1
			except KeyError:
				D[y] = [1, set()]
		x = y
shortlist = 0
for y in D.keys():
	if not D[y][0]:
		insort(result, y)
while len(result) > shortlist:
	x = result[shortlist]
	shortlist += 1
	for y in D[x][1]:
		D[y][0] -= 1
		if D[y][0] == 0:
			insort(result, y, lo=shortlist)
print(' '.join(map(str, result)))


import sys
from heapq import heappush, heappop

def get_int(file):
	return int(file.readline().strip())

def get_int_array(file):
	return list(map(int, file.readline().strip().split(' ')))

def fav_seq(partials):
	dependencies = {}
	depended_by = {}
	order = []
	empties = []
	for partial in partials:
		if partial[-1] not in depended_by:
			depended_by[partial[-1]] = set()
		if partial[0] not in dependencies:
			dependencies[partial[0]] = set()
		for p in range(len(partial) - 1):
			part = partial[p]
			nxt = partial[p + 1]
			if part not in depended_by:
				depended_by[part] = set([nxt])
			else:
				depended_by[part].add(nxt)
			if nxt not in dependencies:
				dependencies[nxt] = set([part])
			else:
				dependencies[nxt].add(part)
	to_del = []
	for (key, val) in dependencies.items():
		if not len(val):
			heappush(empties, key)
			to_del.append(key)
	while to_del:
		del dependencies[to_del.pop()]
	while empties:
		tmp = heappop(empties)
		order.append(tmp)
		for val in depended_by[tmp]:
			dependencies[val].remove(tmp)
			if not len(dependencies[val]):
				heappush(empties, val)
				to_del.append(val)
		while to_del:
			del dependencies[to_del.pop()]
	return ' '.join(list(map(str, order)))

def main():
	file = sys.stdin
	M = get_int(file)
	sequences = []
	for i in range(M):
		k = get_int(file)
		sequences.append(get_int_array(file))
	res = fav_seq(sequences)
	print(res)
main()


import queue
nodes = set()
edges = set()
n = int(input())
for i in range(n):
	k = int(input())
	seq = list(map(int, input().split()))
	for j in range(k):
		nodes.add(seq[j])
	for j in range(k - 1):
		edges.add((seq[j], seq[j + 1]))
indegree = {node: 0 for node in nodes}
adj = {node: [] for node in nodes}
for edge in edges:
	indegree[edge[1]] += 1
	adj[edge[0]].append(edge[1])
q = queue.PriorityQueue()
for (node, degree) in indegree.items():
	if degree == 0:
		q.put(node)
order = []
while adj:
	if q.empty():
		print('cycle detected')
		break
	node = q.get()
	order.append(node)
	for child in adj[node]:
		indegree[child] -= 1
		if indegree[child] == 0:
			q.put(child)
	del adj[node]
print(*order)


from collections import namedtuple
import sys
num = int(input().strip())
lines = []
for line in sys.stdin:
	lines.append(list(map(int, line.split(' '))))
del lines[::2]
graph = {}
backwards = {}
for i in range(0, max((len(line) for line in lines)) - 1):
	for line in lines:
		if i + 1 < len(line):
			(src, dest) = (line[i], line[i + 1])
			if dest not in graph:
				graph[dest] = set()
			if src not in backwards:
				backwards[src] = set()
			graph[dest].add(src)
			backwards[src].add(dest)
s = sorted(set([line[0] for line in lines if line[0] not in graph.keys()]))
l = []
while len(s) > 0:
	new = s.pop(0)
	l.append(new)
	if new in backwards.keys():
		for dest in backwards[new]:
			graph[dest].discard(new)
			if not bool(graph[dest]):
				s.append(dest)
				s.sort()
				graph.pop(dest, None)
print(' '.join((str(i) for i in l)))


from collections import defaultdict as dd
import heapq
N = int(input().strip())
child = dd(set)
parent = dd(set)
toproc = []
seq = []
for _ in range(N):
	K = int(input().strip())
	L = [int(x) for x in input().strip().split(' ')]
	for (p, c) in zip(L[:-1], L[1:]):
		child[p].add(c)
		parent[c].add(p)
for n in child:
	if len(parent[n]) == 0:
		heapq.heappush(toproc, n)
while len(toproc) > 0:
	n = heapq.heappop(toproc)
	seq.append(n)
	for c in child[n]:
		parent[c].discard(n)
		if len(parent[c]) == 0:
			heapq.heappush(toproc, c)
print(' '.join((str(x) for x in seq)))


from heapq import *
g = {}
h = {}
for _ in range(int(input())):
	input()
	a = map(int, input().split())
	p = next(a)
	for i in a:
		g.setdefault(p, set()).add(i)
		h.setdefault(i, set()).add(p)
		p = i
n = sorted(set(g) - set(h))
a = []
while n:
	x = heappop(n)
	a.append(x)
	if x not in g:
		continue
	for i in g.pop(x):
		h[i].discard(x)
		if not h[i]:
			heappush(n, i)
print(*a)


import bisect

class Node:

	def __init__(self, n):
		self.n = n
		self.next = []
		self.prev = []
		self.nactivation = 0

	def arc(self, dest):
		self.next.append(dest)
		dest.prev.append(self)

	def __str__(self):
		return str(self.n)

	def __repr__(self):
		return str(self.n)

	def __lt__(self, other):
		return self.n > other.n
N = int(input())
nodesdict = {}
for i in range(N):
	input()
	prev = None
	for n in map(int, input().split(' ')):
		cur = nodesdict.get(n)
		if cur == None:
			cur = Node(n)
			nodesdict[n] = cur
		if prev != None:
			prev.arc(cur)
		prev = cur
toprocess = []
for node in nodesdict.values():
	if len(node.prev) == 0:
		bisect.insort(toprocess, node)
R = []
while len(toprocess) != 0:
	cur = toprocess.pop()
	R.append(str(cur.n))
	for node in cur.next:
		node.nactivation += 1
		if node.nactivation == len(node.prev):
			bisect.insort(toprocess, node)
print(' '.join(R))


def LexTopoSort(graph):
	degree = {}
	for node in graph:
		degree[node] = 0
	for node in graph:
		for edge in graph[node]:
			degree[edge] += 1
	source_queue = []
	for node in degree:
		if degree[node] == 0:
			source_queue.append(node)
	answer = []
	while source_queue:
		next_node = min(source_queue)
		answer.append(next_node)
		source_queue.remove(next_node)
		for edge in graph[next_node]:
			degree[edge] -= 1
			if degree[edge] == 0:
				source_queue.append(edge)
	return answer

def main():
	num_inputs = int(input())
	sequence_graph = {}
	for i in range(num_inputs):
		input()
		seq = [int(x) for x in input().split()]
		for num in range(len(seq)):
			if seq[num] not in sequence_graph:
				sequence_graph[seq[num]] = []
			if num + 1 < len(seq):
				sequence_graph[seq[num]].append(seq[num + 1])
	repaired_sequence = LexTopoSort(sequence_graph)
	print(' '.join([str(x) for x in repaired_sequence]))
main()


class MinHeap:

	def __init__(self, size):
		self.A = []
		self.A.append(None)
		self.A.append(None)
		for i in range(size):
			self.A.append(None)
		self.n = 0

	def get_min(self):
		return self.A[1]

	def insert(self, t):
		self.n += 1
		self.A[self.n] = t
		self.heapify_up(self.n)

	def delete_min(self):
		e = self.A[1]
		self.A[1] = self.A[self.n]
		self.A[self.n] = None
		self.n -= 1
		self.heapify_down(1)
		return e

	def heapify_up(self, i):
		while i > 1 and self.A[self.parent(i)] > self.A[i]:
			(self.A[i], self.A[self.parent(i)]) = (self.A[self.parent(i)], self.A[i])
			i = self.parent(i)

	def heapify_down(self, i):
		while self.left(i) <= self.n:
			if self.right(i) > self.n:
				m = self.left(i)
			elif self.A[self.left(i)] < self.A[self.right(i)]:
				m = self.left(i)
			else:
				m = self.right(i)
			if self.A[i] <= self.A[m]:
				return
			(self.A[i], self.A[m]) = (self.A[m], self.A[i])
			i = m

	@staticmethod
	def parent(i):
		return i // 2

	@staticmethod
	def left(i):
		return 2 * i

	@staticmethod
	def right(i):
		return 2 * i + 1

	def __str__(self):
		return str(self.A)

def mathishard(B):
	L = []
	outgoing = {}
	incoming = {}
	length = 0
	for lists in B:
		length += len(lists)
		for elem in lists:
			if elem not in outgoing.keys():
				outgoing[elem] = []
			if elem not in incoming.keys():
				incoming[elem] = 0
		if len(lists) >= 2:
			for i in range(len(lists) - 1):
				outgoing[lists[i]].append(lists[i + 1])
				incoming[lists[i + 1]] += 1
	S = MinHeap(length)
	for i in incoming.keys():
		if incoming[i] == 0:
			S.insert(i)
	while S.get_min() != None:
		n = S.delete_min()
		L.append(n)
		u = outgoing[n]
		for following in outgoing[n]:
			u = u[1:]
			incoming[following] -= 1
			if incoming[following] == 0:
				S.insert(following)
		outgoing[n] = u
	return L
n = int(input())
seqs = [[] for _ in range(n)]
for i in range(n):
	k = int(input())
	seqs[i] = list(map(int, input().split(' ')))
print(' '.join((str(i) for i in mathishard(seqs))))


def min_seq_(arr):
	has_before = dict()
	is_before = dict()
	for a in arr:
		x = a[0]
		if x not in has_before:
			has_before[x] = set()
		is_before[x] = is_before.get(x, set()) | {a[1]}
		for (i, x) in enumerate(a[1:-1], 1):
			has_before[x] = has_before.get(x, set()) | {a[i - 1]}
			is_before[x] = is_before.get(x, set()) | {a[i + 1]}
		x = a[-1]
		if x not in is_before:
			is_before[x] = set()
		has_before[x] = has_before.get(x, set()) | {a[-2]}
	candidates = {k for (k, v) in has_before.items() if not v}
	for k in candidates:
		aa_ = has_before.pop(k)
	b = []
	length = len(is_before.keys() | has_before.keys())
	for _ in range(length):
		first = min(candidates)
		b.append(first)
		candidates.discard(first)
		a = is_before.pop(first)
		for x in a:
			has_before[x].discard(first)
			if not has_before[x]:
				candidates.add(x)
				aa_ = has_before.pop(x)
	return b

def min_seq(arr):
	has_before = dict()
	is_before = dict()
	for a in arr:
		for (i, x) in enumerate(a):
			has_before[x] = has_before.get(x, set()) | set(a[:i])
			is_before[x] = is_before.get(x, set()) | set(a[i + 1:])
	candidates = {k for (k, v) in has_before.items() if not v}
	for k in candidates:
		aa_ = has_before.pop(k)
	b = []
	length = len(is_before)
	for _ in range(length):
		first = min(candidates)
		b.append(first)
		candidates.discard(first)
		a = is_before.pop(first)
		for x in a:
			if len(has_before[x]) > 1:
				has_before[x].discard(first)
			else:
				candidates.add(x)
				aa_ = has_before.pop(x)
	return b
n = int(input().strip())
copies = []
for _ in range(n):
	k = input()
	a = list(map(int, input().strip().split()))
	copies.append(a)
result = min_seq_(copies)
print(' '.join(map(str, result)))


import math
import os
import random
import re
import sys, array

def favoriteSequence(arr):
	return 0
ar_count = int(input())
res = list()
q = []
maxCapacity = 1000001
grd = [[0] for i in range(0, maxCapacity)]
index = array.array('i', (0 for i in range(0, maxCapacity)))
maxVal = -1
for i in range(ar_count):
	prev = 0
	lengthArr = int(input())
	ar = list(map(int, input().rstrip().split()))
	for j in range(lengthArr):
		val = ar[j]
		maxVal = val if val > maxVal else maxVal
		if j != 0:
			if grd[prev][0] == 0:
				grd[prev][0] = val
			else:
				grd[prev].append(val)
			index[val] += 1
		prev = val
i = 1
for i in range(1, maxVal):
	if index[i] == 0 and grd[i][0] != 0:
		q.append(i)
i = 0
while len(q) > 0:
	next = q.pop(0)
	res.append(next)
	size = len(grd[next])
	for i in range(0, size):
		node = grd[next][i]
		index[node] -= 1
		if index[node] == 0:
			q.insert(0, node)
			q.sort()
if len(res) > 0:
	res = str(res).strip('[]')
	print(res.replace(',', ''))


from collections import defaultdict
n = int(input())
before_maps = defaultdict(set)
after_maps = defaultdict(set)
for _ in range(n):
	k = int(input())
	sequence = map(int, input().split())
	prev = 0
	for num in sequence:
		if prev:
			before_maps[num].add(prev)
		after_maps[prev].add(num)
		prev = num
m = []
actives = set((active for active in after_maps[0] if not before_maps[active]))
while actives:
	next_step = sorted(actives)[0]
	actives.remove(next_step)
	for step in after_maps[next_step]:
		before_maps[step].remove(next_step)
	actives.update((active for active in after_maps[next_step] if not before_maps[active]))
	m.append(next_step)
print(' '.join(map(str, m)))


from collections import defaultdict
n = int(input())
before_maps = defaultdict(set)
after_maps = defaultdict(set)
for _ in range(n):
	k = int(input())
	sequence = map(int, input().split())
	prev = 0
	for num in sequence:
		if prev:
			before_maps[num].add(prev)
		after_maps[prev].add(num)
		prev = num
m = []
actives = set((active for active in after_maps[0] if not before_maps[active]))
while actives:
	next_step = sorted(actives)[0]
	actives.remove(next_step)
	for step in after_maps[next_step]:
		before_maps[step].remove(next_step)
	actives.update((active for active in after_maps[next_step] if not before_maps[active]))
	m.append(next_step)
print(' '.join(map(str, m)))


import heapq
import collections

def HAVOC(seq):
	g = collections.defaultdict(list)
	in_deg = collections.defaultdict(int)
	maxkj = -1
	for row in seq:
		prev = row[0]
		for i in range(len(row)):
			maxkj = max(row[i], maxkj)
			if i > 0:
				g[prev].append(row[i])
				in_deg[row[i]] += 1
			prev = row[i]
	l = [i for i in range(1, maxkj + 1) if in_deg[i] == 0 and g[i]]
	heapq.heapify(l)
	result = []
	while l:
		top = heapq.heappop(l)
		result.append(top)
		for x in range(len(g[top])):
			node = g[top][x]
			in_deg[node] -= 1
			if in_deg[node] == 0:
				heapq.heappush(l, node)
	return ' '.join(map(str, result))
n = int(input())
seq = []
for _ in range(n):
	k = input()
	seq.append(list(map(int, input().strip().split(' '))))
print(HAVOC(seq))


from collections import defaultdict
n = int(input())
before_maps = defaultdict(set)
after_maps = defaultdict(set)
for _ in range(n):
	k = int(input())
	sequence = map(int, input().split())
	prev = 0
	for num in sequence:
		if prev:
			before_maps[num].add(prev)
		after_maps[prev].add(num)
		prev = num
m = []
actives = set((active for active in after_maps[0] if not before_maps[active]))
while actives:
	next_step = sorted(actives)[0]
	actives.remove(next_step)
	for step in after_maps[next_step]:
		before_maps[step].remove(next_step)
	actives.update((active for active in after_maps[next_step] if not before_maps[active]))
	m.append(next_step)
print(' '.join(map(str, m)))


import sys
import math
import collections
import heapq

class node:

	def __init__(self, val):
		self.val = val
		self.incomming = set()
		self.outcomming = set()

	def __str__(self):
		strin = [n.val for n in self.incomming]
		strout = [n.val for n in self.outcomming]
		return f'val={self.val}, in={strin}, out={strout}'
N = int(input())
(pairs, nodes) = (set(), {})
for _ in range(N):
	K = int(input())
	arr = list(map(int, input().split()))
	for i in range(len(arr) - 1):
		pairs.add((arr[i], arr[i + 1]))
for (a, b) in pairs:
	if a not in nodes:
		nodes[a] = node(a)
	if b not in nodes:
		nodes[b] = node(b)
	if nodes[b] not in nodes[a].outcomming:
		nodes[a].outcomming.add(nodes[b])
	if nodes[a] not in nodes[b].incomming:
		nodes[b].incomming.add(nodes[a])
start = []
ret = []
for n in nodes:
	if not nodes[n].incomming:
		heapq.heappush(start, (nodes[n].val, nodes[n]))
while start:
	(n, node) = heapq.heappop(start)
	for out in node.outcomming:
		out.incomming.remove(node)
		if not out.incomming:
			heapq.heappush(start, (out.val, out))
	ret.append(node.val)
print(' '.join(map(str, ret)))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq
N = int(input())
freq = [0] * 10 ** 6
grid = []
for i in range(N):
	K = input()
	A = list(map(int, input().split()))
	for a in A:
		freq[a] += 1
	grid.append(A)
take_pos = [1] * N
heap = []
for i in range(N):
	heapq.heappush(heap, (grid[i][0], i))

def push(pos):
	if take_pos[pos] < len(grid[pos]):
		heapq.heappush(heap, (grid[pos][take_pos[pos]], pos))
		take_pos[pos] += 1
aside = {}
sequence = []
while heap:
	(no, pos) = heapq.heappop(heap)
	if not aside.get(no) or freq[no] != len(aside[no]):
		if not aside.get(no):
			aside[no] = []
		aside[no].append(pos)
		if len(aside[no]) == freq[no]:
			for pos2 in aside[no]:
				push(pos2)
			sequence.append(no)
			del aside[no]
print(' '.join(map(str, sequence)))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


from collections import defaultdict
import heapq
n = int(input())
byhead = defaultdict(set)
bytail = defaultdict(set)
vertices = set()
nonsources = set()
for _ in range(n):
	k = int(input())
	sublist = list(map(int, input().split()))
	currhead = sublist[0]
	vertices.add(currhead)
	for x in sublist[1:]:
		byhead[currhead].add(x)
		bytail[x].add(currhead)
		currhead = x
		vertices.add(x)
		nonsources.add(x)
sourcesset = vertices.difference(nonsources)
sources = []
for x in sourcesset:
	heapq.heappush(sources, x)
unlisted = defaultdict(lambda : True)
toprint = []
while len(sources) > 0:
	tolist = heapq.heappop(sources)
	for x in byhead[tolist]:
		bytail[x].discard(tolist)
		if len(bytail[x]) == 0 and unlisted[x]:
			unlisted[x] = False
			heapq.heappush(sources, x)
	toprint.append(tolist)
print(' '.join(list(map(str, toprint))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.incoming_edges = 0
		self.succ = set()
N = int(input())
nodes = {}
starts_of_list = set()
parentless_nodes = set()

def binary_search(l, value):
	low = 0
	high = len(l) - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid] > value:
			high = mid - 1
		elif l[mid] < value:
			low = mid + 1
		else:
			return True
	return False

def getOrCreateNode(i):
	if i in nodes:
		return nodes[i]
	nodes[i] = Node(i)
	return nodes[i]

def make_nodes(input_list):
	parent = getOrCreateNode(input_list[0])
	starts_of_list.add(parent.data)
	child = getOrCreateNode(input_list[1])
	if child.data not in parent.succ:
		child.incoming_edges += 1
		parent.succ.add(child.data)
	parentless_nodes.add(child.data)
	for i in range(1, len(input_list) - 1):
		parent = child
		child = getOrCreateNode(input_list[i + 1])
		parentless_nodes.add(child.data)
		if child.data not in parent.succ:
			child.incoming_edges += 1
			parent.succ.add(child.data)
for _ in range(N):
	K = int(input())
	make_nodes(list(map(int, input().split())))
heap = list(starts_of_list - parentless_nodes)
heapq.heapify(heap)
nums = []
while len(heap) > 0:
	smallest = heapq.heappop(heap)
	smallestNode = nodes[smallest]
	nums.append(smallest)
	for nInt in smallestNode.succ:
		n = nodes[nInt]
		n.incoming_edges -= 1
		if n.incoming_edges == 0 and (not binary_search(heap, n.data)):
			heapq.heappush(heap, n.data)
print(' '.join(list(map(str, nums))))


from collections import defaultdict
n = int(input())
before_maps = defaultdict(set)
after_maps = defaultdict(set)
for _ in range(n):
	k = int(input())
	sequence = map(int, input().split())
	prev = 0
	for num in sequence:
		if prev:
			before_maps[num].add(prev)
		after_maps[prev].add(num)
		prev = num
m = []
actives = set((active for active in after_maps[0] if not before_maps[active]))
while actives:
	next_step = sorted(actives)[0]
	actives.remove(next_step)
	for step in after_maps[next_step]:
		before_maps[step].remove(next_step)
	actives.update((active for active in after_maps[next_step] if not before_maps[active]))
	m.append(next_step)
print(' '.join(map(str, m)))


import sys

def find_first_elems(follow_dct):
	return sorted([x for x in follow_dct.keys() if follow_dct[x] == {}])

def remove_edges(v, nbr_dct, follow_dct):
	follow_dct.pop(v, None)
	first_elems = []
	next_elems = nbr_dct.pop(v, None)
	if next_elems is not None:
		for key in next_elems:
			follow_dct[key].pop(v, None)
			if follow_dct[key] == {}:
				first_elems.append(key)
		Q.extend(first_elems)
N = input().rstrip()
nbr_dict = {}
follow_dict = {}
for i in range(int(N)):
	K = input().rstrip()
	seq = list(map(int, input().rstrip().split()))
	if seq[0] not in follow_dict.keys():
		follow_dict[seq[0]] = {}
	for i in range(len(seq) - 1):
		if seq[i] not in nbr_dict.keys():
			nbr_dict[seq[i]] = {seq[i + 1]: 0}
		elif seq[i + 1] not in nbr_dict[seq[i]]:
			nbr_dict[seq[i]][seq[i + 1]] = 0
		if seq[i + 1] not in follow_dict.keys():
			follow_dict[seq[i + 1]] = {seq[i]: 0}
		elif seq[i] not in follow_dict[seq[i + 1]]:
			follow_dict[seq[i + 1]][seq[i]] = 0
Q = find_first_elems(follow_dict)
while len(Q) > 0:
	print(Q[0], end=' ')
	remove_edges(Q[0], nbr_dict, follow_dict)
	del Q[0]
	Q = sorted(Q)