Fişierul intrare/ieşire:lesbulan.in, lesbulan.outSursăBursele Agora 2006
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Lesbulan

Servicile secrete ale SUA au informatii despre zona unde se invarte teroristul Lesbulan. Acesta se ascunde intr-o serie de N buncare care nu pot fi infiltrate. Buncarele sunt legate prin M drumuri. Singura solutie pentru neutralizarea lui ar fi bombardarea buncarelor. Pentru a nu cauza scandal international, doar un buncar poate fi bombardat intr-o noapte, dupa bombardare buncarul nu va fi distrus ci refacut imediat pentru ca Lesbulan este un om plin de resurse. Serviciile secrete au mai aflat ca pentru a nu ii fi desconspirata locatia el schimba in fiecare seara buncarul in care isi va petrece noaptea si se va deplasa intr-un buncar vecin celui din noaptea anterioara.

Cerinta

Ajutati serviciile secrete sa determine daca exista o strategie de neutralizare a lui Lesbulan!

Date de intrare

In fisierul de intrare lesbulan.in vom avea pe prima linie un numar intreg T care corespunde numarului de configuratii de buncare din fisier. Pe urmatoarele linii se vor afla T configuratii posibile ale buncarelor. Prima linie a fiecarui test va contine doua numere intregi N si M. Pe urmatoarele M linii vor fi situate cate doua numere intregi X si Y, separate intre ele printr-un spatiu reprezentand existenta unui drum intre buncarele X si Y. Testele vor fi separate de o linie goala asa cum se vede in exemplu.

Date de iesire

Fisierul de iesire lesbulan.out va contine T linii, linia a i-a avand numarul 1 daca pentru configuratia a i-a din fisierul de intrare exista o strategie de neutralizare a lui Lesbulan sau un 0 in caz contrar.

Restrictii si precizari

  • 1 ≤ T ≤ 10
  • 1 ≤ N ≤ 50

Exemplu

lesbulan.inlesbulan.out
2
2 1
1 2
 
4 6
1 2
1 3
1 4
2 3
2 4
3 4
1
0

Explicatie

O strategie pentru primul caz este bombardarea de doua ori a orasului 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content