Demək olar ki, ən qısa yol

Verilmiş yönsüz və çəkisiz qrafda iki zirvə s və t seçilmişdir. s-dən t-yə olan ən qısa yolun uzunluğu d olaraq təyin edilsin. Demək olar ki, ən qısa yol dedikdə, uzunluğu d olan yoldan keçən heç bir kənardan istifadə etməyən ən qısa yol nəzərdə tutulur. Demək olar ki, ən qısa yolun uzunluğunu tapın və ya belə bir yol mövcud deyilsə, -1 çıxarın.

Giriş məlumatları

Birinci sətir dörd tam ədədi ehtiva edir: zirvələrin sayı n, kənarların sayı m (n, m ≤ 10^5) və zirvələrin nömrələri s və t (1 ≤ s, t ≤ n). Sonrakı m sətirin hər biri iki tam ədəd a və b ehtiva edir ki, bu da yönsüz kənarı (a, b) təyin edir.

Çıxış məlumatları

Zirvələr s və t arasında demək olar ki, ən qısa yolun uzunluğunu çıxarın. Əgər belə bir yol mövcud deyilsə, -1 çıxarın.

İzah

Zirvələr 1 və 3 arasında ən qısa yolun uzunluğu 2-dir. Ən qısa yoldan keçən kənarlar qırmızı ilə göstərilmişdir. Demək olar ki, ən qısa yol qırmızı kənarlardan istifadə etməyən ən qısa yoldur. Demək olar ki, ən qısa yol mavi rənglə göstərilmişdir və onun uzunluğu 5-dir.