Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given $K$ permutations of integers $1$ through $N$. For each $i$ ($1 ≤ i ≤ K$), the $i$-th permutation is denoted by $A_{i,1}, A_{i,2}, \ldots, A_{i,N}$.

Construct a directed acyclic graph with $N$ nodes (numbered $1$ through $N$) such that:
Each of the given permutations is a valid topological sort of the graph. Formally, for each valid $k$ and each $i, j$ ($1 ≤ i < j ≤ N$), there is no edge from the node $A_{k,j}$ to the node $A_{k,i}$.
The outdegree of each node is at most $1$.
The number of nodes with indegree $0$ is the smallest possible.

If there are multiple solutions, you may find any one.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
$K$ lines follow. For each $i$ ($1 ≤ i ≤ K$), the $i$-th of these lines contains $N$ space-separated integers $A_{i,1}, A_{i,2}, \ldots, A_{i,N}$.

------  Output ------
For each test case, print two lines.
The first of these lines should contain one integer ― the minimum number of nodes with indegree $0$.
The second line should contain $N$ space-separated integers $v_{1}, v_{2}, \ldots, v_{N}$ describing your graph in the following way: for each valid $i$, if $v_{i} = 0$, there is no outgoing edge from the $i$-th node; otherwise, there is an edge from the $i$-th node to the $v_{i}$-th node.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 500$
$1 ≤ K ≤ 100$
$1 ≤ A_{i,j} ≤ N$ for each valid $i,j$
the sum of $N$ over all test cases does not exceed $2,000$

------  Subtasks ------
Subtask #1 (20 points):
$N ≤ 20$
$K ≤ 10$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2

2 2

1 2

2 1

2 2

1 2

1 2
----- Sample Output 1 ------ 
2

0 0

1

2 0
----- explanation 1 ------ 
Example case 1: The graph must consist of just two disconnected nodes, since no edges are allowed. Hence, there are two nodes with indegree $0$.

Example case 2: The graph may contain an edge from node $1$ to node $2$. Then, there is only one node with indegree $0$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Data structures

Flows and cuts


Solutions:
def bpm(u, match, seen, n, graph):
	for j in range(n):
		if graph[u][j] == 1 and seen[j] == False:
			seen[j] = True
			if match[j] == -1 or bpm(match[j], match, seen, n, graph):
				match[j] = u
				return True
	return False

def solve():
	(n, k) = [int(i) for i in input().split()]
	valid_points = [[1 for i in range(n)] for j in range(n)]
	for i in range(n):
		valid_points[i][i] = 0
	for i in range(k):
		perm = [int(d) - 1 for d in input().split()]
		for j in range(1, n):
			for r in range(j - 1, -1, -1):
				valid_points[perm[j]][perm[r]] = 0
	result = 0
	match = [-1] * n
	for i in range(n):
		seen = [False] * n
		if bpm(i, match, seen, n, valid_points):
			result += 1
	print(n - result)
	final_ans = [0] * n
	for i in range(n):
		if match[i] != -1:
			final_ans[match[i]] = i + 1
	for i in final_ans:
		print(i, end=' ')
	print()
t = int(input())
while t > 0:
	solve()
	t -= 1


def hopcroft_karp(U, adj):
	upair = {}
	vpair = {}
	inf = float('inf')
	dist = {}

	def bfs() -> bool:
		q = []
		for u in U:
			if upair.get(u) is not None:
				dist[u] = inf
			else:
				dist[u] = 0
				q.append(u)
		dist[None] = inf
		while q:
			q2 = []
			for u in q:
				if dist[u] < dist[None]:
					for v in adj[u]:
						if dist.get(vpair.get(v), inf) == inf:
							dist[vpair.get(v)] = dist[u] + 1
							q2.append(vpair.get(v))
			q = q2
		return dist[None] != inf

	def dfs(u):
		if u is not None:
			for v in adj[u]:
				if dist.get(vpair.get(v), inf) == dist.get(u, inf) + 1:
					if dfs(vpair.get(v)):
						vpair[v] = u
						upair[u] = v
						return True
			dist[u] = inf
			return False
		return True
	while bfs():
		for u in U:
			if upair.get(u) is None:
				dfs(u)
	return upair

def sol(n, k, ps):
	ps = list(set(ps))
	k = len(ps)
	adj = {u: set(ps[0][i + 1:]) for (i, u) in enumerate(ps[0])}
	seens = {j: set() for j in range(1, k)}
	for i in range(n - 1, -1, -1):
		for j in range(1, k):
			u = ps[j][i]
			adj[u] = set((v for v in adj[u] if v in seens[j]))
			seens[j].add(u)
	us = hopcroft_karp(range(1, n + 1), adj)
	res = [0] * n
	for (u, v) in us.items():
		res[u - 1] = v
	return (sum((1 for x in res if x == 0)), res)

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		ps = []
		for i in range(k):
			ps.append(tuple((int(x) for x in input().split())))
		(z, res) = sol(n, k, ps)
		print(z)
		print(' '.join((str(x) for x in res)))
main()


import sys
input = sys.stdin.readline

def FindMinimum(Ans):
	Minimum = float('inf')
	key = -1
	for (i, j) in Ans.items():
		if len(j) < Minimum:
			key = i
			Minimum = len(j)
	return key
from collections import defaultdict
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	count = 0
	Ans = {}
	for i in range(N):
		x = list((x for x in range(1, N + 1)))
		Ans[i + 1] = x
	for i in range(K):
		X = list(map(int, input().split()))
		for i in range(N):
			Ans[X[i]] = set(Ans[X[i]]) & set(X[i + 1:])
	Counter = defaultdict(lambda : 0)
	for i in Ans.values():
		for j in i:
			Counter[j] += 1
	OutDegree = defaultdict(lambda : 0)
	InDegree = defaultdict(lambda : 0)
	while len(Ans.keys()) > 0:
		T = FindMinimum(Ans)
		for (i, j) in Ans.items():
			if len(j) == len(Ans[T]) and i != j:
				Min1 = float('inf')
				for k in j:
					if Counter[k] < Min1:
						Min1 = Counter[k]
				Min2 = float('inf')
				for z in Ans[T]:
					if Counter[z] < Min2:
						Min2 = Counter[z]
				if Min1 >= Min2:
					T = i
		FLAG = 0
		Min = float('inf')
		index = -1
		for i in Ans[T]:
			if Counter[i] < Min:
				Min = Counter[i]
				index = i
		if index != -1:
			OutDegree[T] = index
			InDegree[index] = 1
			val = index
			FLAG = 1
			for i in Ans[T]:
				Counter[i] -= 1
			del Ans[T]
		if FLAG == 0:
			OutDegree[T] = 0
			for i in Ans[T]:
				Counter[i] -= 1
			del Ans[T]
		else:
			for (i, j) in Ans.items():
				if val in j:
					Counter[val] = -1
					j.remove(val)
	count = 0
	for i in range(1, N + 1):
		if OutDegree[i] == 0:
			count += 1
	print(count)
	for i in range(1, N + 1):
		print(OutDegree[i], end=' ')
	print()


def main():
	for _ in range(int(input())):
		(n, k) = list(map(int, input().split()))
		p = [list(map(int, input().split())) for i in range(k)]
		ans = [-1] * n
		as1 = [0] * n
		visited = [False] * n
		freqin = [0] * n
		for i in p:
			for j in range(n):
				if ans[i[j] - 1] == -1:
					ans[i[j] - 1] = [i[j] - 1, set(i[j + 1:])]
				else:
					ans[i[j] - 1][1] = ans[i[j] - 1][1].intersection(i[j + 1:])
		for i in range(n):
			ans[i][1] = list(ans[i][1])
		for i in ans:
			for j in i[1]:
				freqin[j - 1] += 1
		ans.sort(key=lambda a: len(a[1]))
		maxi = max(freqin)
		visited = [False] * n
		i1 = -1
		for i in range(len(ans)):
			mini = maxi + 1
			ans1 = -1
			sans1 = -1
			k1 = 0
			m = min(ans, key=lambda a: ([visited[j - 1] for j in a[1]].count(False), -len(a[1])))
			for j in range(len(m[1])):
				if not visited[m[1][j] - 1] and mini >= freqin[m[1][j] - 1]:
					mini = freqin[m[1][j] - 1]
					ans1 = m[1][j]
					k1 = 1
			if k1 == 1:
				as1[m[0]] = ans1
				visited[ans1 - 1] = True
			ans.remove(m)
		print(visited.count(False))
		print(' '.join(list(map(str, as1))))
main()


import time
from copy import deepcopy

class HopcroftKarp(object):

	def __init__(self, graph):
		self._matching = {}
		self._dfs_paths = []
		self._dfs_parent = {}
		self._graph = deepcopy(graph)
		self._left = set(self._graph.keys())
		self._right = set()
		for value in self._graph.values():
			self._right.update(value)
		for vertex in self._left:
			for neighbour in self._graph[vertex]:
				if neighbour not in self._graph:
					self._graph[neighbour] = set()
					self._graph[neighbour].add(vertex)
				else:
					self._graph[neighbour].add(vertex)

	def __bfs(self):
		layers = []
		layer = set()
		for vertex in self._left:
			if vertex not in self._matching:
				layer.add(vertex)
		layers.append(layer)
		visited = set()
		while True:
			layer = layers[-1]
			new_layer = set()
			for vertex in layer:
				if vertex in self._left:
					visited.add(vertex)
					for neighbour in self._graph[vertex]:
						if neighbour not in visited and (vertex not in self._matching or neighbour != self._matching[vertex]):
							new_layer.add(neighbour)
				else:
					visited.add(vertex)
					for neighbour in self._graph[vertex]:
						if neighbour not in visited and (vertex in self._matching and neighbour == self._matching[vertex]):
							new_layer.add(neighbour)
			layers.append(new_layer)
			if len(new_layer) == 0:
				return layers
			if any((vertex in self._right and vertex not in self._matching for vertex in new_layer)):
				return layers

	def __dfs(self, v, index, layers):
		if index == 0:
			path = [v]
			while self._dfs_parent[v] != v:
				path.append(self._dfs_parent[v])
				v = self._dfs_parent[v]
			self._dfs_paths.append(path)
			return True
		for neighbour in self._graph[v]:
			if neighbour in layers[index - 1]:
				if neighbour in self._dfs_parent:
					continue
				if neighbour in self._left and (v not in self._matching or neighbour != self._matching[v]) or (neighbour in self._right and (v in self._matching and neighbour == self._matching[v])):
					self._dfs_parent[neighbour] = v
					if self.__dfs(neighbour, index - 1, layers):
						return True
		return False

	def maximum_matching(self, keys_only=False):
		while True:
			layers = self.__bfs()
			if len(layers[-1]) == 0:
				break
			free_vertex = set([vertex for vertex in layers[-1] if vertex not in self._matching])
			del self._dfs_paths[:]
			self._dfs_parent.clear()
			for vertex in free_vertex:
				self._dfs_parent[vertex] = vertex
				self.__dfs(vertex, len(layers) - 1, layers)
			if len(self._dfs_paths) == 0:
				break
			for path in self._dfs_paths:
				for i in range(len(path)):
					if i % 2 == 0:
						self._matching[path[i]] = path[i + 1]
						self._matching[path[i + 1]] = path[i]
		if keys_only:
			self._matching = {k: v for (k, v) in self._matching.items() if k in self._left}
		return self._matching
tests = int(input())
while tests:
	tests -= 1
	(n, K) = map(int, input().split())
	Yes = {}
	No = {}
	d = {}
	l = []
	graph = {}
	for i in range(1, n + 1):
		d[i] = 0
		Yes[i] = []
		No[i] = []
	for _ in range(K):
		l.append(list(map(int, input().split())))
	for i in range(K):
		for j in range(n):
			Yes[l[i][j]] += l[i][j + 1:]
			No[l[i][j]] += l[i][:j]
	for i in Yes:
		Yes[i] = set(Yes[i]) - set(No[i])
		if len(Yes[i]) != 0:
			graph[i + 10 ** 9] = Yes[i]
	g = HopcroftKarp(graph).maximum_matching(keys_only=True)
	for i in g:
		d[i - 10 ** 9] = g[i]
	d = dict(sorted(d.items()))
	print(list(d.values()).count(0))
	print(*d.values())