Nosaukums
Noziegums un sods (noziegums_un_sods)
Laika limits
1.00s
Atmiņas limits
64.0 MB
Grūtība
50%

Definīcija

Gudrinieku ciemā tika aplaupīta banka! Policija izmanto visus resursus, lai noķērtu zagli.

Ciemā ir n dažādi krustojumi, sanumurēti ar skaitļiem no 1 līdz n. Vairāki krustojumu pāri ir savienoti ar taisniem ceļa posmiem. Ceļi ir ierīkoti tādā veidā, ka starp katru krustojumu pāri eksistē tieši viens ceļš (kas, iespējams, sastāv no vairākiem posmiem), kas savieno šos krustojumus.

Zaglis atrodas krustojumā Z un policists atrodas krustojumā P. Krustojumā K ir kanalizācijas caurums, caur kuru zaglis var aizbēgt no policista. Gan zaglis, gan policists noskrien vienu ceļa posmu starp diviem krustojumiem vienā minūtē. Gan zaglis, gan policists var brīvi izvēlēties, kur skriet. Katrs no viņiem var arī gaidīt krustojumā. Ja abi satiekas vienā vietā, policists noķer zagli. Ja zaglis var nonākt krustojumā K pirms tas notiek, viņš aizbēg.

Nosakiet, cik laika policistam ir pietiekams, lai noķērtu zagli, vai arī vai zaglim izdosies aizbēgt, pirms viņu noķers.


Ievaddatu raksturojums

Pirmajā rindā dots naturāls skaitlis n, krustojumu skaits (3 ≤ n ≤ 105).

Otrajā rindā doti ceļu krustojumu numuri Z, P un (1 ≤ Z, P, K ≤ n, ≠ P, ≠ K, K ≠ Z).

Nākamajās n - 1 rindās doti ceļu posmu apraksti. i-tajā rindā doti divi naturāli skaitļi ai un bi, kas nozīmē, ka krustojumi ar attiecīgiem numuriem ir savienoti ar ceļa posmu.


Izvaddatu raksturojums

Ja policists noteikti var noķert zagli, izvadiet mazāko minūšu skaitu, kas pietiekams, lai noķērtu zagli (pie jebkurām zagļa kustībām). Ja zaglim ir iespējams aizbēgt, izvadiet –1.


Paraugdati

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

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

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

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