Alqoritmin mürəkkəbliyi
Petr öz xüsusi alqoritmindən istifadə edərək istiqamətli qraf G üçün mühüm bir məsələni həll etmək istəyir. Bu qraf n zirvə və m oxdan ibarətdir. Təəssüf ki, Petr alqoritminin mürəkkəbliyini qiymətləndirməyi bilmir. O, yalnız bilir ki, bu mürəkkəblik F(n) böyümə qaydası ilə əlaqəlidir, burada F(n) qraf G-də s zirvəsindən t zirvəsinə qədər uzunluğu n olan yolların sayını göstərir. Petr F(n)-i minimal dərəcəli çoxhədli ilə məhdudlaşdırmaq istəyir, yəni elə minimal qeyri-mənfi tam ədəd k tapmaq istəyir ki, bəzi sabit C üçün F(n) ≤ C * n^k bərabərsizliyi bütün müsbət n üçün yerinə yetirilsin.
Ona bu işdə kömək edin.
Giriş məlumatları
Birinci sətirdə dörd ədəd yazılıb: n, m, s, t (1 ≤ n, m ≤ 10^5). Qrafın zirvələri 1-dən n-ə qədər nömrələnib. Növbəti m sətirdə hər birində iki ədəd - növbəti oxun başlanğıc və son zirvələrinin nömrələri boşluqla ayrılmış şəkildə yazılıb. Qrafda təkrarlanan oxlar ola bilməz, amma döngələr ola bilər.
Çıxış məlumatları
Şərti təmin edən minimal tam ədəd k-ni çıxarın. Əgər belə ədəd mövcud deyilsə, "-1" çıxarın.