== include(page="template/taskheader" task_id="aby") ==
Se spune ca odata, demult , in vechea tara Lapestina exista un castel magic.
De curand maleficul Rainbowdash din Rasiel a rapit-o pe printesa Lolita, iar eroul nostru, Abu, este pregatit sa faca orice
ca sa o salveze. Dupa o calatorie epica cu multe peripetii Abu afla in final ca printesa este tinuta prizoniera de Rainbowdash in ultima camera
a castelului pomenit anterior.
Castelul este format din N camere si M pereti magici ce fac legatura dintre aceste camere, peretii acestia sunt speciali si
un om cu vointa puternica (cum ar fi eroul nostru) poate trece prin ei, dar numai intr-un sens prestabilit, daca el incearca sa treaca
in sens invers, se va lovi cu capul de perete, din pacate.
Deoarece eroul nostru are un dispozitiv magic de teleportare, numit lucoj el nu trebuie decat sa ajunga la Lolita
trecand prin pereti, incepand din prima camera si aventura lui va lua sfarsit, intorcandu-se cu printesa acasa.
Din pacate pentru noi treaba se complica, Rainbowdash a aflat de planul lui Abu,si fiind un
magician puternic el are la dispozitie urmatorul truc pentru a-l impiedica sa
ajunga la Lolita: de fiecare data can Abu trece printr-un perete, el poate alege o camera, iar toti peretii ce
au o fata spre acea camera isi vor schimba sensul magic.
Abu a obtinut in calatoriile lui T harti dintre care una sigura corespunde castelului, dar nefiind sigur care dintre ele , el va roaga sa-i spuneti
pentru fiecare daca este posibil sa-si salveze printesa, presupunand ca maleficul Rainbowdash nu-si greseste miscarile.
De curand maleficul Rainbowdash din Rasiel a rapit-o pe printesa Lolita, iar eroul nostru, Abu, este pregatit sa faca orice ca sa o salveze. Dupa o calatorie epica cu multe peripetii Abu afla in final ca printesa este tinuta prizoniera de Rainbowdash in ultima camera a castelului pomenit anterior.
Castelul este format din $N$ (numerotate de la 0 la $N$ - 1) camere si $M$ pereti magici ce fac legatura dintre aceste camere. Peretii acestia sunt speciali si un om cu vointa puternica (cum ar fi eroul nostru) poate trece prin ei, dar numai intr-un sens prestabilit.
Deoarece eroul nostru are un dispozitiv magic de teleportare numit lucoj, el nu trebuie decat sa ajunga la Lolita(aflata in camera $N - 1$) trecand prin pereti incepand din prima camera (numerotata cu $0$) si apoi aventura lui va lua sfarsit, intorcandu-se cu printesa acasa.
Din pacate pentru noi treaba se complica. Rainbowdash a aflat de planul lui Abu, si fiind un magician puternic el are la dispozitie urmatorul truc pentru a-l impiedica sa ajunga la Lolita: Deoarece a rostit niste incantatii magice, de fiecare data cand Abu trece printr-un perete, Rainbowdash este obligat sa aleaga o camera iar toti peretii ce au o fata spre acea camera isi vor schimba sensul magic.
Spre exemplu sa spunem ca avem un castel cu $3$ camere. Exista un perete de la camera $0$ la camera $1$ si un perete de la camera $1$ la camera $2$. Abu nu se poate muta decat din camera $0$ in camera $1$, dupa aceasta, Rainbowdash poate vrajii fie camera $1$ caz in care se schimba sensul peretilor de la $0$ la $1$ si de la $1$ la $2$, sau camera $2$ ,caz in care se schimba sensul peretelui de la camera $1$ la camera $2$. De observat ca in acest caz Abu nu poate sa salveze printesa. Pe de alta parte daca ar mai exista inca un perete de la camera $2$ la camera $1$, orice ar face Rainbowdash , Abu poate ajunge in camera $2$.
Abu a obtinut in calatoriile lui $T$ harti dintre care una sigur corespunde castelului, dar nefiind sigur care dintre ele , el va roaga sa-i spuneti pentru fiecare daca este posibil sa-si salveze printesa, presupunand ca maleficul Rainbowdash nu-si greseste miscarile.
h2. Date de intrare
Fişierul de intrare $aby.in$ contine pe prima linie un numar $T$ de teste, iar pe urmatoarele linii, pentru fiecare test , avem : o line cu numerele $N$ si $M$ iar apoi $M$ linii continand perechi de numere $X$ si $Y$ semnificand faptul ca exista un perete orientat de la camera $X$ la camera $Y$.
h2. Date de ieşire
În fişierul de ieşire $aby.out$ veti afisa $T$ linii, fiecare linie $i$ continand raspunsul pentru configuratia de la testul $i$, si anume $1$ daca Abu poate ajunge in ultima camera, iar in caz contrat $0$.
h2. Restricţii si precizari
* $Intre teste exista cate o linie libera$
* $Pot exista mai multi pereti intre doua camere$
* $Pot exista pereti cu ambele capete in aceeasi camera$
* $Dupa fiecare mutare a lui Abu, Rainbowdash este obligat sa aleaga si el o camera si s-o vrajeasca$
* $1 ≤ T ≤ 103$
* $2 ≤ N ≤ 12$
* $0 ≤ M ≤ 150$
* $Abu si Rainbowdash isi fac miscarile optim.$
* $Lolita nu are buletin.$
h2. Exemplu
table(example). |_. aby.in |_. aby.out |
| 5
3 2
0 1
1 2
3 3
0 1
1 2
2 1
5 9
0 1
1 2
2 1
1 3
4 1
3 2
4 2
3 4
4 2
6 16
0 2
0 3
1 3
1 4
1 5
2 0
2 1
2 3
3 2
3 4
4 0
4 1
4 5
5 1
5 2
5 3
6 15
0 1
1 0
1 5
2 1
2 3
2 4
3 1
3 3
3 5
4 0
4 1
4 4
4 5
5 2
5 4
| 0
1
0
1
0
|
h3. Explicaţie
Primele doua teste au fost explicate in enunt, iar la al 3-lea, Abu se va muta de la 0 la 1, Rainbowdash va vrajii camera 3, Abu se va muta de la 1 la 2, rainbowdash va vrajii din nou camera 3, apoi Abu se muta de la 2 la 1... si tot asa, astfel abu nu va ajunge niciodata in ultima camera.
La al 4-lea test Abu se va muta in 2, daca rainbowdash vrajeste camera 2, abu s-ar duce in 5, asadar el trebuie sa vrajeasca camera 1(fiind dublu legata de 5), de aici abu se duce in 3, de unde orice ar face Rainbowdash , Abu va castiga in maxim 3 mutari.
La al 5-lea test abu se poate plimba intre camera 0 si camera 1, la fiecare mutare a sa vrajitorul vrajeste camera 5, lasandu-l pe Abu blocat.
== include(page="template/taskfooter" task_id="aby") ==
