==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/taskheader" task_id="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!
 
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
 
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 |
 
h3. Explicatie
 
O strategie pentru primul caz este bombardarea de doua ori a orasului 1.
 
==Include(page="template/taskfooter" task_id="lesbulan")==

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

992