C. Сул Ой Тогтоолт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

PMP ICPC World Finals орж яваад том машины зогсоол дээр төөрж орхив. Түүнд багийнхаа автобусыг олоход нь туслана уу.

Зогсоол нь 1-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг уулзвартай бөгөөд тэдгээрийн заримыг хооронд нь холбосон $m$ ширхэг хоёр чиглэлт зам бий. $k$ ширхэг уулзвар дээр ICPC-н сайн дурын хөтчүүд байгаа ба тэд хүмүүст зорьсог газартаа хүрэхэд шаардлагатай замууды нь хэлж өгдөг. Хөтчүүдийн байрлал нь тодорхой/тогтмол/ бөгөөд нэг уулзвар дээр хамгийн ихдээ нэг л хөтөч байдаг.

PMP ямар нэгэн хөтчөөс зам асуухад тухайн хөтөч нь PMP-д багийнхаа автобусанд очиход шаардлагатай замыг бүтнээр хэлж өгөх боловч PMP тун сул ой тогтоолттой тул тэрээр тухайн замаас хамгийн ихдээ $q$ уулзвары нь(одоо зогсож буй уулзварыг оруулахгүй) л цээжилж чадна. PMP ямар нэгэн хөтчөөс зам асуух болгондоо өөрийнхөө сул санах ойтойг хэлээд одоо тэдний зогсож буй уулзвараас автобус буй уулзвар хүртэл хамгийн ихдээ $q$ уулзвар бүхий зам байгаа эсэхийг асуудаг ба хэрэв тийм зам байхгүй бол тэр хөтөч нь түүнийг автобуснаас хамгийн ихдээ $q$ уулзварын зайтай газар зогсож буй хөтөчрүү аваачдаг. Хөтөчүүд орчноо маш сайн мэддэг ба PMP-д ямагт хамгийн сайн замуудыг зааж өгдөг. Тиймээс хэрэв автобусандаа очих зам байгаа л бол PMP түүний нь заавал олно гэдэгт итгэлтэй байж болно.

PMP хамгийн эхэнд $s$-р зогсоол дээр байгаа ба автобус нь $t$-р зогсоол дээр бий. Мөн $s$-р зогсоол дээр заавал хөтөч байх болно. Таны даалгавар бол PMP автобусаа олж очиход шаардлагатай хамгийн бага $q$-н утгыг олох юм.

Оролт

Эхний мөрөнд уулзваруудын тоо, тэднийг холбож буй замуудын тоо болон хөтчүүдийн тоонуудыг илэрхийлэх $n, m, k(2<=n<=10^5, 0<=m<=2*10^5, 1<=k<=n)$ гэсэн 3-н тоо байрлана. Дараагийн $k$ мөрөнд хөтчүүдийн байрлаж буй уулзваруудын дугаар байрлана.

Дараачийн $m$ мөрөнд замуудын мэдээлэл байрлана. Эдгээр мөрнүүдийн $i$-р нь $u_i, v_i(1<=u_i, v_i<=n, u_i!=v_i)$ -ийг агуулах ба энэ нь $u_i$-р уулзвар нь $v_i$ уулзвартай холбоотой гэсэн үг.

Сүүлийн мөрөнд $s, t(1<=s, t<=n, s!=n)$ буюу эхлэх уулзвар болон очих уулзварын утгууд байна. $s$-р мөрөнд заавал хөтөч байрлах болно.

Гаралт

$q$-н хамгийн бага утгыг хэвлэ. Хэрвээ PMP автобусаа олж очих боломжгүй бол -1 хэвлэ.

Орчуулсан: devman

Жишээ тэстүүд

Оролт
6 6 3
1 3 6
1 2
2 3
4 2
5 6
4 5
3 4
1 6
Гаралт
3
Оролт
6 5 3
1 5 6
1 2
2 3
3 4
4 5
6 3
1 5
Гаралт
3

Тэмдэглэл

Хамгийн эхний жишээг доор үзүүлэв. Цэнхэр уулзварууд нь сайн дурынхан байрлах газар. Хэрэв PMP тасалдалтай зураасыг дагаж явбал тэр $q = 3$ байх увтобусуудад хүрнэ.

% zurag

Хамгийн сүүлийн жишээнд PMP 6-р уулзварыг хоорондын уулзвар болгон хэрэглэх тул хариу нь 3.

Сэтгэгдлүүдийг ачааллаж байна...