Yollar#2203
Gadyukino şəhərinin meri son böyük təmirdən sonra yolların vəziyyətini yoxlamağa qərar verdi. Bunun üçün o, hər bir yolu hər iki istiqamətdə keçmək istəyir.
Merə kömək edin ki, hər bir yolu ən azı bir dəfə hər iki istiqamətdə keçən ən qısa marşrutu planlaşdırsın.
Gadyukino şəhərində ədəd kəsişmə və ədəd yol var. Hər bir yol iki müxtəlif kəsişməni birləşdirir. Hər iki kəsişmə arasında ən çox bir yol olur.
Məlumdur ki, yollar vasitəsilə istənilən kəsişmədən digərinə getmək mümkündür.
Giriş faylında və tam ədədləri (1 \leq n \leq 10^4, 1 \leq m \leq 10^5), ardından cüt tam ədəd a_i və b_i — -ci yolun birləşdirdiyi kəsişmələrin nömrələri verilir.
Çıxışda — minimal marşrutun uzunluğunu və ardından s+1 tam ədəd — kəsişmələrin nömrələrini ardıcıllıqla getmənin düzülüşünü çap edin.
Nümunə 1