Təlim

Мирко və Slavko Xorvatiyada keçiriləcək illik tandem velomarafonuna ciddi hazırlaşırlar. Onlar məşq üçün marşrut seçməlidirlər.

Ölkədə $N$ şəhər və $M$ yol var. Hər bir yol iki şəhəri birləşdirir və hər iki istiqamətdə hərəkət etmək mümkündür. Dəqiq N-1 yol daş döşənmişdir, qalan yollar isə döşənməmiş cığırdır. Xoşbəxtlikdən, yol şəbəkəsi elə qurulub ki, istənilən iki şəhəri yalnız daş döşənmiş yollardan ibarət bir yol birləşdirir. Başqa sözlə, $N$ şəhər və N-1 daş döşənmiş yol ağac strukturunu təşkil edir.

Əlavə olaraq, hər bir şəhərdə ən çox $10$ yol bitir.

Məşq marşrutu müəyyən bir şəhərdə başlayır, bəzi yollardan keçir və başladığı şəhərdə bitir. Mirko və Slavko yeni şəhərləri ziyarət etməyi sevirlər, buna görə də belə bir qayda qoyublar: heç vaxt eyni yerdən və eyni yoldan iki dəfə keçməmək. Məşq marşrutu istənilən şəhərdə başlaya bilər və bütün şəhərlərin hamısından keçmək məcburiyyətində deyil.

Tandemdə arxa oturacaqda oturmaq daha asandır, çünki velosipedçi ön oturacaqda oturan tərəfdaş tərəfindən küləkdən qorunur. Buna görə də Mirko və Slavko hər şəhərdə yerlərini dəyişirlər. Məşq zamanı bərabər yük almaq üçün onlar cüt sayda yoldan ibarət marşrut seçməlidirlər.

Mirko və Slavkonun rəqibləri bəzi cığırları bloklamağa qərar veriblər ki, göstərilən tələblərə cavab verən məşq marşrutu qurmaq mümkün olmasın. Hər bir cığırın bloklanma qiyməti məlumdur (müsbət tam ədəd). Daş döşənmiş yolları bloklamaq mümkün deyil.

Şəhərlər və yolların təsviri əsasında, göstərilən tələblərə cavab verən məşq marşrutunun mövcud olmaması üçün yolları bloklamaq üçün lazım olan ən az ümumi dəyəri tapan proqram yazın.