Катанın Məskunlaşanları
İlin oyunu olan 1995-ci ildəki "Katanın Müstəmləkəçiləri" oyununda oyunçular, naməlum səhrada yollar, məskənlər və şəhərlər tikərək adada üstünlük qazanmağa çalışırlar.
Siz proqram təminatı inkişaf etdirən bir şirkətdə işləyirsiniz və bu şirkət yeni olaraq bu oyunun kompüter versiyasını hazırlamağa qərar verib. Siz isə oyunun xüsusi qaydalarından birini həyata keçirmək üçün seçilmisiniz:
Oyunun sonunda ən uzun yolu tikən oyunçu əlavə iki qalibiyyət xalı qazanır.
Problem ondadır ki, oyunçular adətən yalnız bir xətti yol deyil, mürəkkəb yol şəbəkələri qururlar. Buna görə də, ən uzun yolu müəyyənləşdirmək asan iş deyil (baxmayaraq ki, insanlar bunu adətən dərhal görürlər).
Orijinal oyunla müqayisədə burada sadələşdirilmiş bir məsələni nəzərdən keçirəcəyik: Sizə zirvələr (şəhərlər) və zirvələri birləşdirən uzunluğu 1 olan kənarların (yolların) dəsti təqdim olunur. Ən uzun yol, şəbəkədə iki dəfə istifadə olunmayan kənarların olduğu ən uzun yol kimi müəyyən edilir. Lakin zirvələr bir neçə dəfə ziyarət edilə bilər.
Giriş məlumatları
Bir və ya bir neçə testdən ibarətdir. Hər bir testin ilk sətiri iki tam ədəd ehtiva edir: zirvələrin sayı n (2 ≤ n ≤ 25) və kənarların sayı m (1 ≤ m ≤ 25). Növbəti m sətir m kənarı təsvir edir. Hər bir kənar, onunla birləşdirilən iki zirvənin nömrələri ilə verilir. Zirvələr 0-dan n - 1-ə qədər nömrələnir. Kənarlar istiqamətsizdir. Zirvələrin dərəcəsi üç və ya daha azdır. Şəbəkə mütləq əlaqəli deyil. Giriş n və m üçün iki 0 ilə tamamlanır.
Çıxış məlumatları
Hər bir test üçün ayrıca sətirdə ən uzun yolun uzunluğunu çıxarın.
