== include(page="template/taskheader" task_id="caroiaj") ==

Serban si Teodora joaca un joc pe o tabla patratica cu $N$ X $N$ celule. Pe fiecare celula a tablei este cate un jeton colorat cu un numar scris pe el, astfel incat, tabla privita de sus, arata precum un caroiaj. O mutare consta in alegerea unui jeton de pe una din cele 2 * $N$ - 1 diagonale principale, daca de pe acea diagonala nu a mai fost ales pana la momentul mutarii niciun alt jeton. Incepe jocul. Cei doi muta alternativ.
Bunicul, amintindu-si ca cei doi vor participa la Concursul National de Informatica "Adolescent Grigore Moisil", ii motiveaza pe cei doi sa lucreze in echipa, astfel incat la finalul celor 2 * $N$-1 mutari, sa fi fost alese jetoane diferite(considerand jetoanele alese de Serban si Teodora). Doua jetoane se considera diferite daca numerele de pe ele difera.

Serban si Teodora joaca un joc pe o tabla patratica cu $N$ x $N$ celule. Pe fiecare celula a tablei este cate un jeton colorat cu un numar scris pe el, astfel incat, tabla privita de sus, arata precum un caroiaj. O mutare consta in alegerea unui jeton de pe una din cele $2 * N - 1$ diagonale principale, daca de pe acea diagonala nu a mai fost ales pana la momentul mutarii niciun alt jeton. Incepe jocul. Cei doi muta alternativ.
Bunicul, amintindu-si ca cei doi vor participa la Concursul National de Informatica "Adolescent Grigore Moisil", ii motiveaza pe cei doi sa lucreze in echipa, astfel incat la finalul celor $2 * N - 1$ mutari, sa fi fost alese jetoane diferite(considerand jetoanele alese de Serban si Teodora). Doua jetoane se considera diferite daca numerele de pe ele difera.

Sa se spuna pentru $T$ caroiaje daca cei doi pot muta astfel incat la final toate jetoanele sa fie diferite. In cazul in care exista solutie, sa se afiseze si o modalitate de alegere.
h2. Date de intrare

Fişierul de intrare $caroiaj.in$ va contine pe prima linie un numar natural $T$, reprezentand numarul de caroiaje. Pe urmatoarea linie se afla un numar natural $N$, reprezentand latura caroiajului. Urmatoarele $N$ linii contin $N$ numere,linia $i$ + 1 reprezentand cea de-a $i$-a linie a caroiajului.Aceasta configuratie se repeta de $T$ ori.

Fişierul de intrare $caroiaj.in$ va contine pe prima linie un numar natural $T$, reprezentand numarul de caroiaje. Pe urmatoarea linie se afla un numar natural $N$, reprezentand latura caroiajului. Urmatoarele $N$ linii contin $N$ numere, linia $i + 1$ reprezentand cea de-a $i$-a linie a caroiajului. Aceasta configuratie se repeta de $T$ ori.

h2. Date de ieşire

În fişierul de ieşire $caroiaj.out$ vor fi $T$ linii. Cea de-a $i$-a linie reprezinta raspunsul pentru testul $i$. Daca exista solutie, se va afisa mesajul "DA", urmat de 2 * $N$ - 1 numere, reprezentand numerele alese de pe fiecare diagonala in parte. Prima diagonala principala se considera a fi coltul stanga-jos al caroiajului, iar ultima diagonala principala se considera a fi coltul dreapta-sus al caroiajului. In cazul in care pentru testul $i$ nu exista solutie, atunci linia $i$ va contine mesajul "Bunicul este dezamagit!".

În fişierul de ieşire $caroiaj.out$ vor fi $T$ linii. Cea de-a $i$-a linie reprezinta raspunsul pentru testul $i$. Daca exista solutie, se va afisa mesajul "DA", urmat de $2 * N - 1$ numere, reprezentand numerele alese de pe fiecare diagonala in parte. Prima diagonala principala se considera a fi coltul stanga-jos al caroiajului, iar ultima diagonala principala se considera a fi coltul dreapta-sus al caroiajului. In cazul in care pentru testul $i$ nu exista solutie, atunci linia $i$ va contine mesajul "Bunicul este dezamagit!".

h2. Restricţii

* Pentru toate testele de la evaluare, $T$ = 44.
* $N$ <= 300.
* Numerele din matrice sunt cuprinse intre 1 si 10^9.

* Pentru toate testele de la evaluare, $T = 44$.
* $1 ≤ N ≤ 300$.
* Numerele din matrice sunt cuprinse intre $1$ si $10^9^$.

* In cazul in care exista solutie, numerele corespunzatoare jetoanelor alese se vor afisa in ordinea crescatoare a diagonalelor principale pe care sunt pozitionate.
* Daca exista mai multe solutii, se poate afisa oricare.