Fişierul intrare/ieşire:cp.in, cp.outSursăHappy Coding 2008
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.8 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.incp.out
1
3 3
1 2
2 3
3 1
NU
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content