Ən qısa yol

İstiqamətlənməmiş qraf verilmişdir. a təpəsindən b təpəsinə ən qısa yolu tapın.

Giriş verilənləri

İlk sətirdə iki tam n və m (1 ≤ n ≤ 5 * 10^4, 1 ≤ m ≤ 10^5) ədədləri - uyğun olaraq təpələrin və tillərin sayı verilir. İkinci sətirdə a və b tam ədədləri - uyğun olaraq başlanğıc və son təpələr verilir. Daha sonra dilləri ifadə edən m sətir verilir.

Çıxış verilənləri

a və b arasında yol yoxdursa -1 çap edin. Əks halda ilk sətirdə bu təpələr arasında ən qisa yolun uzunluğunu ifadə edən l ədədini, ikinci sətirdə isə l + 1 ədədini yolun keçdiyi təpələrin sayını çap edin.

Nümunələr