Zəif k-bağlılıq
Aynaya, gələcəyin dünya proqramlaşdırma çempionu olaraq, çox məsuliyyətli bir vəzifə həvalə edilib. N-rayonunun hökuməti ona şəhərlər arasında yolların tikinti planını hazırlamağı tapşırır. Plana əsasən, bütün yollar birtərəflidir, lakin iki şəhər arasında müxtəlif istiqamətlərdə bir neçə yol ola bilər. Aynanın belə minimal k hesablaması lazımdır ki, ona verilən plan zəif k-əlaqəli olsun.
Hökumət planı zəif k-əlaqəli adlandırır, əgər aşağıdakı şərt yerinə yetirilirsə: hər hansı iki fərqli şəhər üçün birindən digərinə k dəfədən çox qayda pozmadan getmək mümkündür. Qayda pozuntusu mövcud yolda əks istiqamətdə getməkdir. Hər hansı iki şəhər arasında, bəlkə də bir neçə dəfə qayda pozaraq getməyin mümkün olduğu təmin edilir.
Giriş verilənləri
Giriş faylının ilk sətirində iki ədəd 2 ≤ n ≤ 300 və 1 ≤ m ≤ 10^5 - plandakı şəhərlərin və yolların sayı verilir. Növbəti m sətirdə müvafiq yolun başladığı və bitdiyi şəhərlərin nömrələri verilir.
Çıxış verilənləri
Çıxış faylına minimal k yazın ki, giriş faylında verilən plan zəif k-əlaqəli olsun.