Zooloji eksperiment
Vasya zoologiya dərnəyində iştirak edir və burada şuşpançiklər üzərində təcrübələr aparır. Təcrübələrdən birində o, iki şuşpançiki istiqamətsiz qraf şəklində olan bir labirintə yerləşdirir. Hər saniyə hər bir şuşpançik cari mövqeyinə qonşu olan zirvələrdən birini seçərək ora tullanır. Şuşpançiklər qonşu zirvələrin hər birini bərabər ehtimalla seçirlər. Onlar eyni labirintdə olsalar da, bir-birinə heç bir reaksiya vermirlər və tamamilə müstəqil hərəkət edirlər. Ən azından Vasya belə düşünür. Bu hipotezi yoxlamaq üçün o, orta hesabla şuşpançiklərin eyni zirvədə nə qədər vaxt keçirdiyini ölçmək qərarına gəlir. Səhvlərdən qaçmaq üçün Vasya, şuşpançiklərin uzun müddət ərzində eyni zirvədə olduqları saniyələrin payını orta hesabla götürür. Vasya həmçinin hesab edir ki, şuşpançiklər bir-birinə heç bir reaksiya verməsələr də, o qədər dəqiq ritm saxlayırlar ki, bu müddət ərzində tamamilə sinxron tullanırlar. Bu ölçünün nəzəri hesablamasını aparmaq lazımdır.
Məhdudiyyətlər
2 ≤ N ≤ 100
1 ≤ M ≤ 10000
Giriş verilənləri
Giriş faylının ilk sətiri labirintdəki zirvələrin və kənarların sayını göstərən iki tam ədəd: N və M -dən ibarətdir.
Sonrakı M sətirin hər biri kənarla birləşdirilmiş zirvələrin nömrələrini göstərən iki tam ədəd ehtiva edir (1-dən N -ə qədər). Qrafda döngələr, paralel kənarlar və təcrid olunmuş zirvələr olmadığına zəmanət verilir.
Növbəti sətir 1-dən N -ə qədər olan iki tam ədəd ehtiva edir - şuşpançiklərin əvvəlcə yerləşdirildiyi zirvələrin nömrələri. Bu nömrələr üst-üstə düşə bilər. Şuşpançiklər hərəkətə eyni anda başlayırlar.
Çıxış verilənləri
Tək bir ədəd çıxarın - Vasya'nın fərziyyələri doğru olarsa, şuşpançiklərin eyni zirvədə keçirməli olduqları vaxtın payı.