Recover Square

All submissions for this problem are available.
###Read problems statements in [Hindi](http://www.codechef.com/download/translated/S19ELTST/hindi/RECOVER.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/S19ELTST/mandarin/RECOVER.pdf), [Russian](http://www.codechef.com/download/translated/S19ELTST/russian/RECOVER.pdf), [Vietnamese](http://www.codechef.com/download/translated/S19ELTST/vietnamese/RECOVER.pdf) and [Bengali](http://www.codechef.com/download/translated/S19ELTST/bengali/RECOVER.pdf) as well. A long time ago, a grid with $N$ rows and $N$ columns had mysteriously vanished. The cells of this grid contain integers $1$ through $N\cdot N$ in some order. You do not know this order, but some information remains to this day: $M$ pairs of cells with Manhattan distance $1$ or $2$. You should find a grid satisfying the following conditions (or decide that it does not exist):  The cells of the grid contain all integers from $1$ to $N^2$.  For each given pair $(u, v)$, the cells containing $u$ and $v$ have Manhattan distance $1$ or $2$.  There are no other pairs of cells with Manhattan distance $1$ or $2$. If there are multiple possible 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 $M$.  Each of the following $M$ lines contains two spaceseparated integers $u$ and $v$ describing a pair of cells at distance $1$ or $2$. ### Output For each test case:  If there is no solution, print a single line containing the integer $1$.  Otherwise, print $N$ lines containing $N$ spaceseparated integers each. The $j$th integer on the $i$th line should denote the number in the $i$th row and $j$th column of the grid. ### Constraints  $1 \le T \le 200$  $1 \le N \le 200$  $0 \le M \le 3 \cdot 10^5$  $1 \le u, v \le N^2$  $u \neq v$  all pairs $(u, v)$ are distinct  the sum of $M$ over all test cases does not exceed $10^6$ ### Example Input ``` 2 2 6 1 3 1 4 1 2 3 4 3 2 4 2 3 6 3 8 3 1 3 9 3 5 3 2 8 1 ``` ### Example Output ``` 1 3 2 4 1 ``` ### Explanation **Example case 1:** Note that there are many possible solutions. **Example case 2:** A solution satisfying all constraints on given pairs may exist, but there would always be some other pair of cells with distance $1$ or $2$ too.Author:  bciobanu 
Editorial  https://discuss.codechef.com/problems/RECOVER 
Tags  bciobanu, constructive, mediumhard, observations, pruning, snckel19, taran_1407 
Date Added:  25112018 
Time Limit:  1 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, 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. 