logic

Într-o zi a venit la mine un coleg din clasa a X-a şi mi-a propus un joc de logică. Mi-a arătat următoarea figură:

Pe ea am numerotat segmentele, pentru a fi mai clară noţiunea de segment. Eu am la dispoziţie un creion care se află pe hârtie în zona exterioară şi trebuie să trasez curbe pe foaie, fără să ridic creionul, astfel încât să trec prin toate segmentele (fără extremităţi) exact o dată. La sfârşit trebuie să mă aflu tot în exterior. Liniile(curbele) mele se pot intersecta.
Am început şi am încercat de mai multe ori, dar n-am reuşit.

Acum, când am mai crescut mi-am demostrat că nu se poate, dar am văzut că pentru alte figuri se poate. De exemplu aceasta:

Eu m-am prins de ce uneori merge şi alteori nu, dar vreau să văd dacă voi puteţi să vă prindeţi. De aceea o să vă dau câteva figuri şi pentru fiecare trebuie să răspundeţi cu DA sau NU, dacă se poate sau nu trasa o curbă de tipul descris mai sus.

Cerinţă

Scrieţi un program care răspunde cu DA sau NU pentru figurile propuse de mine.

Date de intrare

Fişierul de intrare logic.in are următoarea structură:

• pe prima linie se află numărul $T$ de figuri
• pe următoarele $T$ grupuri de linii se află datele celor $T$ figuri, după cum urmează:
• pe prima linie a grupului se află valoarea lui $N$ reprezentând numărul de linii şi de coloane din matrice.
• pe următoarele $N$ linii se află câte $N$ numere separate printr-un spaţiu (numere întregi între $0$ şi $255$ inclusiv), reprezentând elementele matricei.

Această matrice codifică figura astfel :

Definim o zonă ca fiind o parte continuă a matricei care conţine acelaşi număr şi este aria maximă cu această proprietate. Altfel spus, două căsuţe alăturate (care diferă la o singură coordonată printr-o unitate) care conţin acelaşi număr, se lipesc. Astfel, în interiorul zonei nu vor exista segmente. La aceste zone se mai adaugă şi exteriorul matricei ca fiind o nouă zonă. În matrice pot fi zone cu acelaşi număr, dar care nu au legătură şi se consideră două zone diferite.

Segmentele sunt segmente de dreaptă care separă două zone şi sunt maxime ca lungime (adică nu putem considera două segmente unul în prelungirea celuilalt, în loc de unul singur). De exemplu, figura definită prin:

3
1 1 2
1 2 2
1 1 2

arată ca în desenul de mai jos (am numerotat şi segmentele):

Se vede din figură că între zona $1$ şi $2$ există $5$ segmente. Între $1$ şi exterior $3$ segmente, iar între $2$ şi exterior tot $3$ segmente. De remarcat că segmentul $10$ este compus din $3$ segmente mici, dar noi îl considerăm unul singur, conform definiţiei.

Date de ieșire

În fişierul logic.out se vor scrie $T$ linii, corespunzătoare fiecărui test. Pe fiecare linie va fi scris DA sau NU în funcţie de testul respectiv, dacă se poate trasa o linie de tipul cerut sau nu.

Restricții și precizări

• $1 \leq T \leq 10$;
• $1 \leq N \leq 100$;

Exemplu

logic.in

2				
2				
1 2
3 4
4
1 1 2 2
1 1 2 2
3 4 4 1
3 4 4 1

logic.out

DA
NU

Explicație

Cele două figuri sunt primele $2$ exemple.