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.
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 trecand prin pereti, incepand din prima camera si aventura lui va lua sfarsit, intorcandu-se cu printesa acasa.
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: de fiecare data cand 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.
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 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 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.
h2. Date de intrare
Fişierul de intrare $aby.in$ ...
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$ ...
Î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
