Tom & Jerry joacă un joc într-un graf neorientat cu N noduri (numerotate de la 1 la N).
Tom alege unul dintre nodurile grafului şi se poziţionează în acest nod. Apoi Jerry alege şi el unul dintre nodurile grafului (eventual acelaşi) şi se poziţionează în acel nod.
După aceste poziţionări “strategice”, începe jocul efectiv. Tom & Jerry efectuează mutări alternativ. La fiecare mutare, ei se pot deplasa din nodul în care se află în orice alt nod învecinat (două noduri sunt învecinate dacă există o muchie între ele) sau pot rămâne pe loc (în acelaşi nod).
Tom este cel care efectuează prima mutare şi scopul lui este de a-l prinde pe Jerry. Astfel, Tom câştigă jocul dacă ajunge în acelaşi nod al grafului ca şi Jerry. Jerry câştigă jocul dacă poate să fugă de Tom la infinit (adică orice mutare ar efectua Tom, la orice moment, Jerry poate efectua la rândul lui o mutare prin care să evite să ajungă în aceeaşi poziţie ca şi Tom).
Cerinţă
Pentru un graf dat, determinaţi dacă Tom are strategie sigură de câştig.
Date de intrare
Prima linie a fişierului tj.in conţine numărul natural T, reprezentând numărul de grafuri descrise în continuare. Un graf este descris pe o succesiune de linii din fişierul de intrare, după cum urmează. Prima linie conţine numerele naturale N şi M reprezentând numărul de noduri, respectiv numărul de muchii ale grafului. Fiecare dintre următoarele M linii conţine câte 2 numere naturale a şi b, având semnificaţia că există muchie între nodurile a şi b. Între descrierile a două grafuri consecutive din fişierul de intrare se află o linie goală.
Date de ieşire
În fişierul de ieşire tj.out veţi afişa pentru fiecare graf din fişierul de intrare (în ordinea în care sunt descrise grafurile în fişier) DA, în caz că Tom are strategie sigură de câştig, respectiv NU, în caz contrar.
Restricţii
• 1 <= T <= 20
• 1 <= N <= 256
• 0 <= M <= N*(N-1)/2
• Nu există muchie de la un nod la el însuşi.
• Între două noduri ale grafului există cel mult o muchie.
• Cel puţin 60% din teste vor avea N <= 64