| Fişierul intrare/ieşire: | cp.in, cp.out | Sursă | Happy Coding 2008 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cp
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, v1, v2, ..., vk, N (k ≥ 1), astfel incat exista muchiile (1,v1), (vk,N) si (vi,vi+1) (1≤i≤k-1). Nodurile v1, v2, ..., vk 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.
Date de intrare
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.
Date de iesire
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).
Restrictii
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 1000
- N-1 ≤ M ≤ 100000
Exemplu
| cp.in | cp.out |
|---|---|
| 1 3 3 1 2 2 3 3 1 | NU |
