lesbulan

Lesbulan

== include(page="template/taskheader" task_id="lesbulan") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| lesbulan.in | lesbulan.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="lesbulan") ==

==Include(page="template/taskheader" task_id="lesbulan")==
==Include(page="template/raw")==
 
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.
 
h2. Cerinta
 
Ajutati serviciile secrete sa determine daca exista o strategie de neutralizare a lui Lesbulan!
 
 
 
Date de intare
 
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.
 
h2. 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.
 
Restrictie
 
1 <= T <= 10;
1 <= N <= 50.
 
h2. Exemplu
 
 
|lesbulan.in |lesbulan.out |Explicatie |
 
|2 |1 |O strategie pentru primul caz este bombardarea de doua ori a orasului 1 |
|2 1 | | |
|1 2 |0 | |
| | | |
|4 6 | | |
|1 2 | | |
|1 3 | | |
|1 4 | | |
|2 3 | | |
|2 4 | | |
|3 4 | | |
 
 
 
 
 
==Include(page="template/taskfooter" task_id="lesbulan")==