Nosaukums
Sliedes un pārmijas (tram)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

Tramvaju sliežu tīkls sastāv no sliežu posmiem un N krustojumiem. Krustojumi ir numurēti ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Noteiktus krustojumus savieno sliežu posmi. Katrā krustojumā ir pārmija, kas ir pārslēgta uz vienu izejošo sliežu posmu. Ja tramvajs iebrauc krustojumā, tas no krustojuma var izbraukt tikai pa to sliežu posmu, uz kuru ir pārslēgta pārmija. Ja tramvajam nepieciešams braukt pa citu sliežu posmu, tad vadītājam pārmija ir jāpārslēdz. Ar vienu pārmijas pārslēgšanu vadītājs var pārslēgt pārmiju uz jebkuru no izejošajiem sliežu posmiem.

Ja tramvaja vadītājam ir jāaizbrauc no krustojuma A līdz krustojumam B, tad viņš cenšas atrast tādu maršrutu, kurā pārmiju pārslēgšanu skaits būtu mazākais iespējamais.

Uzrakstiet programmu, kas dotiem krustojumiem atrod mazāko nepieciešamo pārmiju pārslēgšanu skaitu maršrutā no viena krustojuma līdz otram!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dotas trīs naturālu skaitļu N(krustojumu skaits, 2 ≤N≤100), A un B(krustojumu - maršruta galapunktu numuri, 1≤A,B≤N) vērtības, kas atdalītas ar tukšumsimboliem.

Katra no nākošajām N ievaddatu rindām satur veselu skaitļu virkni, kur blakus skaitļus atdala tukšumsimboli. Pirmais skaitlis i-tajā rindā Ki(0≤Ki≤N-1) ir sliežu posmu skaits, kas iziet no i-tā krustojuma. Nākošie Ki skaitļi apzīmē to krustojumu numurus uz kuriem iet šie sliežu posmi. Sākotnēji katra pārmija ir pārslēgta uz pirmo no izejošajiem sliežu posmiem.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada vesels skaitlis - mazākais nepieciešamais pārmiju pārslēgšanu skaits. Ja no krustojuma A līdz krustojumam B aizbraukt nav iespējams, jāizvada skaitlis '-1'.

 


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā


Paraugdati

Stdin
3 2 1
2 2 3
2 3 1
2 1 2
Stdout
0

Stdin
3 1 3
1 2
2 1 3
1 2
Stdout
1

Stdin
4 4 2
1 2
1 1
1 4
1 3
Stdout
-1

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.