Fişierul intrare/ieşire:aby.in, aby.outSursă.com 2012 Runda 3
AutorIoan PetcuAdăugată deedp100Edp100 edp100
Timp execuţie pe test0.5 secLimită de memorie66432 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

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.

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.

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.

Exemplu

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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content