== 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 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