Zəif k-birləşiklik

Anya, gələcəyin proqramlaşdırma üzrə dünya çempionu kimi, çox vacib bir tapşırıq alıb. N-region Hökuməti ona şəhərlər arasında yolların qurulması planını verir. Plana görə, bütün yollar bir-tərəflidir, lakin istənilən iki şəhər arasında bir neçə yol ola bilər, bunlar müxtəlif istiqamətlərdə də ola bilər. Anya tapmalıdır ki, plana görə ən kiçik $k$ bütöv ədədi neçedir ki, plan zəif $k$-birləşikdir.

Bir plan zəif $k$-birləşik adlanır, əgər belə bir şərt ödənilirsə: istənilən iki fərqli şəhər üçün, birindən digərinə maksimum $k$ dəfə yol qaydasını pozaraq getmək mümkündür. Qayda pozuntusu mövcud bir yol üzrə əks istiqamətdə hərəkət etməyə deyilir. Zəmanət verilir ki, istənilən iki şəhər arasında, bəlkə də bir neçə dəfə qaydanı pozmaqla getmək mümkündür.