Fişierul intrare/ieşire:	tj.in, tj.out	Sursă	Lot 2005
Autor	Mugurel Ionut Andreica	Adăugată de
Timp execuţie pe test	1.75 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	5/5

Tom & Jerry

Tom si Jerry joaca un joc intr-un graf neorientat cu N noduri (numerotate de la 1 la N). Tom alege unul dintre nodurile grafului si se pozitioneaza in acest nod. Apoi Jerry alege si el unul dintre nodurile grafului (eventual acelasi) si se pozitioneaza in acel nod. Dupa aceste pozitionari strategice, incepe jocul efectiv. Tom si Jerry efectueaza mutari alternativ. La fiecare mutare, ei se pot deplasa din nodul in care se afla in orice alt nod invecinat (doua noduri sunt invecinate daca exista o muchie intre ele) sau pot ramane pe loc (in acelasi nod). Tom este cel care efectueaza prima mutare si scopul lui este de a-l prinde pe Jerry. Astfel, Tom castiga jocul daca ajunge in acelasi nod al grafului ca si Jerry. Jerry castiga jocul daca poate sa fuga de Tom la infinit (adica orice mutare ar efectua Tom, la orice moment, Jerry poate efectua la randul lui o mutare prin care sa evite sa ajunga in aceeasi pozitie ca si Tom).

Cerinta

Pentru un graf dat, determinati daca Tom are strategie sigura de castig.

Date de intrare

Prima linie a fisierului tj.in contine numarul natural T, reprezentand numarul de grafuri descrise in continuare. Un graf este descris pe o succesiune de linii din fisierul de intrare, dupa cum urmeaza. Prima linie contine numerele naturale N si M reprezentand numarul de noduri, respectiv numarul de muchii ale grafului. Fiecare dintre urmatoarele M linii contine cate 2 numere naturale a si b, avand semnificatia ca exista muchie intre nodurile a si b. Intre descrierile a doua grafuri consecutive din fisierul de intrare se afla o linie goala.

Date de iesire

In fisierul de iesire tj.out veti afisa pentru fiecare graf din fisierul de intrare (in ordinea in care sunt descrise grafurile in fisier) DA, in caz ca Tom are strategie sigura de castig, respectiv NU, in caz contrar.