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

Poveste şi cerinţă...

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$ ...

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$ ...

Î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 = 15.
* 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.

h2. Exemplu
table(example). |_. caroiaj.in |_. caroiaj.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|1 3 1 2 3 4 5 6 7 8 9
| DA 7 4 1 2 6

|
h3. Explicaţie

...

Avem matricea
 
1 2 3
4 5 6
7 8 9
 
De pe diagonala principala cu numarul de ordine 1 alegem jetonul cu numarul 7
De pe diagonala principala cu numarul de ordine 2 alegem jetonul cu numarul 4
De pe diagonala principala cu numarul de ordine 3 alegem jetonul cu numarul 1
De pe diagonala principala cu numarul de ordine 4 alegem jetonul cu numarul 2
De pe diagonala principala cu numarul de ordine 5 alegem jetonul cu numarul 6

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