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!
Teksta faila tram.in 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 faila 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.
Teksta faila tram.out 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'.
| tram.in | tram.out |
3 2 1 2 2 3 2 3 1 2 1 2 |
0 |
| tram.in | tram.out |
3 1 3 1 2 2 1 3 1 2 |
1 |
| tram.in | tram.out |
4 4 2 1 2 1 1 1 4 1 3 |
-1 |