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.

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.

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.

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

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

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

Î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

h2. Restricţii si precizari

*  $1 ≤ T ≤ 100$
*  $2 ≤ N ≤ 15$
*  $0 ≤ M ≤ N * N * N$

*  $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 |

| 1
  5 4

| 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

  2 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") ==

8785