lesbulan

Lesbulan

== include(page="template/taskheader" task_id="lesbulan") ==

==Include(page="template/taskheader" task_id="lesbulan")==

Poveste ...
h2. Cerinta
 
...

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. Restrictii

h2. Cerinta

...

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

h2. 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.

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.
 
h2. Restrictii si precizari
 
* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 50$

h2. Exemplu

| lesbulan.in | lesbulan.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. 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 |

== include(page="template/taskfooter" task_id="lesbulan") ==

h3. Explicatie
 
O strategie pentru primul caz este bombardarea de doua ori a orasului 1.
 
==Include(page="template/taskfooter" task_id="lesbulan")==
 
 

992