Fişierul intrare/ieşire: | lesbulan.in, lesbulan.out | Sursă | Bursele Agora 2006 |
Autor | Cosmin Silvestru Negruseri | Adăugată de | |
Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
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.in | lesbulan.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.