Chef and DAG

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/MARCH20/hindi/CHEFDAG.pdf), [Bengali](http://www.codechef.com/download/translated/MARCH20/bengali/CHEFDAG.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/MARCH20/mandarin/CHEFDAG.pdf), [Russian](http://www.codechef.com/download/translated/MARCH20/russian/CHEFDAG.pdf), and [Vietnamese](http://www.codechef.com/download/translated/MARCH20/vietnamese/CHEFDAG.pdf) as well. You are given $K$ permutations of integers $1$ through $N$. For each $i$ ($1 \le i \le 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 \le i \lt j \le 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 spaceseparated integers $N$ and $K$.  $K$ lines follow. For each $i$ ($1 \le i \le K$), the $i$th of these lines contains $N$ spaceseparated 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$ spaceseparated 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 \le T \le 100$  $1 \le N \le 500$  $1 \le K \le 100$  $1 \le A_{i,j} \le 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 \le 20$  $K \le 10$ **Subtask #2 (80 points):** original constraints ### Example Input ``` 2 2 2 1 2 2 1 2 2 1 2 1 2 ``` ### Example Output ``` 2 0 0 1 2 0 ``` ### Explanation **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$.Author:  rahuldugar 
Editorial  https://discuss.codechef.com/problems/CHEFDAG 
Tags  bipartitematching, graphs, march20, medium, rahuldugar, tmwilliamlin 
Date Added:  30052019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 