== include(page="template/taskheader" task_id="cp") ==
Poveste si cerinta...
Se da un graf neorientat, conex, avand $N$ noduri, numerotate de la $1$ la $N$, si $M$ muchii. Nodurile $1$ si $N$ sunt *speciale*. Doi jucatori $(1$ si $2)$ joaca urmatorul joc - ei efectueaza mutari alternativ (jucatorul $1$ efectueaza prima mutare), astfel: jucatorul aflat la mutare alege un nod necolorat al grafului (diferit de $1$ si $N$) si il coloreaza. Jucatorul $1$ coloreaza nodurile cu culoarea *verde*, iar jucatorul $2$ cu culoarea *rosie*. Jocul se termina atunci cand toate nodurile (cu exceptia lui $1$ si $N$) au fost colorate, considerand ca, initial, niciun nod nu este colorat.
Un *drum* in graf este reprezentat de o secventa de noduri $1, v{~1~}, v{~2~}, ..., v{~k~}, N (k ≥ 1)$, astfel incat exista muchiile $(1,v{~1~}), (v{~k~},N)$ si $(v{~i~},v{~i+1~}) (1≤i≤k-1)$. Nodurile $v{~1~}, v{~2~}, ..., v{~k~}$ se numesc *noduri interne* ale drumului.
Daca la sfarsitul jocului exista cel putin un drum ale carui noduri interne sunt toate colorate in *verde* si nu exista niciun drum ale carui noduri interne sunt toate colorate in *rosu*, atunci jucatorul 1 este castigator. Daca la sfarsitul jocului exista cel putin un drum ale carui noduri interne sunt toate colorate in *rosu* si nu exista niciun drum ale carui noduri interne sunt toate colorate in *verde*, atunci jucatorul 2 este castigator.
Daca la sfarsitul jocului nu exista nici un drum ale carui noduri interne sa aiba toate aceeasi culoare sau exista atat un drum cu toate nodurile interne colorate in verde, cat si un drum cu toate nodurile interne colorate in rosu, rezultatul jocului este remiza.
Determinati daca jucatorul $2$ are o strategie sigura de obtinere a victoriei.
h2. Date de intrare
Fisierul de intrare $cp.in$ ...
Prima linie a fisierului de intrare $cp.in$ contine numarul intreg $T$, reprezentand numarul de teste descrise in continuare. Prima linie a unui test contine numerele intregi $N$ si $M$, reprezentand numarul de noduri si numarul de muchii. Urmatoarele $M$ linii contin cate $2$ numere intregi $a$ si $b$, avand semnificatia ca exista o muchie intre nodul numerotat cu $a$ si cel numerotat cu $b$.
h2. Date de iesire
In fisierul de iesire $cp.out$ ...
Pentru fiecare test din fisierul de intrare veti afisa in fisierul de iesire $cp.out$ cate o linie, continand sirul *"DA"* (fara ghilimele), daca jucatorul $2$ are strategie sigura de castig pentru testul respectiv, sau *"NU"* (tot fara ghilimele), daca nu are o astfel de strategie (in acest caz, orice ar face, jucatorul 2 ori va pierde jocul, ori va obtine doar o remiza).
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10$
* $2 ≤ N ≤ 1000$
* $N-1 ≤ M ≤ 100000$
h2. Exemplu
table(example). |_. cp.in |_. cp.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
...
|1
3 3
1 2
2 3
3 1
|NU|
== include(page="template/taskfooter" task_id="cp") ==
