Fişierul intrare/ieşire:tj.in, tj.outSursăLot 2005
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test3.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

Restrictii si precizari

  • 1 ≤ T ≤ 20
  • 1 ≤ N ≤ 256
  • 0 ≤ M ≤ N*(N-1)/2
  • Nu exista muchie de la un nod la el insusi
  • Intre doua noduri ale grafului exista cel mult o muchie
  • Cel putin 60% din teste vor avea N ≤ 64

Exemplu

tj.intj.out
6
2 0          
           
4 4
1 2
1 3
2 3
3 4          
           
3 2
1 2
2 3          
           
2 1
1 2          
           
1 0          
           
4 4
1 2
2 3
3 4
4 1
NU
DA
DA
DA
DA
NU

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content