Ada dövlətləri#1938
Qarışıq feodal dövründə, bir vaxtlar məşhur olan ByteLandia ada dövləti iki güclü baron tərəfindən idarə olunurdu və onların hər biri bəzi şəhərlərə nəzarət edirdi. Bəzi şəhərlər ikitərəfli yollarla birləşdirilib. Müxtəlif baronların nəzarət etdiyi şəhərləri birləşdirən yolda səyahət etmək üçün bir ByteLandia rublu məbləğində rüsum ödəmək lazımdır. Bundan əlavə, cüt nömrəli şəhərlərdən çıxarkən ikiqat rüsum tutulur.
Proqramçı Vasya 1 nömrəli şəhərdə yaşayır. Yay gələndə, o, ByteLandia Proqramçıları Yığıncağı üçün -ci şəhərə səyahət etmək istəyir. O, bu səfərə mümkün qədər az pul xərcləmək istəyir və sənin köməyinə ehtiyacı var.
Birinci sətirdə iki tam ədəd və (1 \leq n, m \leq 100000) — şəhərlərin və yolların sayı verilir.
Növbəti sətirdə ədəd və ya — hər şəhərə hansı baronun nəzarət etdiyini göstərir.
Sonra növbəti sətirində, hər birində iki tam ədəd və (1 \leq a, b \leq n, a \neq b) verilib, şəhərlər və arasında yol olmasını göstərir. Bütün yollar ikitərəflidir.
Əgər heç bir marşrut yoxdursa, yeganə sətrə **impossible** çıxarın. Əks halda, birinci sətirdə minimum xərc və ziyarət olunan şəhərlərin sayını, ikinci sətirdə isə sırayla ziyarət olunan şəhərləri çıxarın. Əgər bir neçə minimal xərcli yol varsa, onlardan istənilən birini çıxara bilərsiniz.
Nümunə 1