Ada dövlətləri
Sərt feodal dövrlərində böyük ada dövləti Baytlandiya mövcud olmuşdur. Ada üzərində hakimiyyət uğrunda iki güclü baron mübarizə aparır. Bu səbəbdən, ölkənin hər bir şəhəri bir baronun nəzarətindədir. Ənənəvi olaraq, bəzi şəhərlər ikitərəfli yollarla birləşdirilib. Baronlar bir-birini sevmədikləri üçün, fərqli hökmdarların şəhərlərini birləşdirən yoldan keçmək üçün bir baytlandiya rublu rüsum ödəmək tələb olunur. Bundan əlavə, cüt nömrəli şəhərlərdən çıxış üçün ikiqat rüsum alınır.
Proqramçı Vasya 1 nömrəli şəhərdə yaşayır. Yayın başlaması ilə o, N nömrəli şəhərə, Baytlandiya proqramçıları toplantısına getməyi planlaşdırır. Aydındır ki, o, bu səfərdə mümkün qədər az pul xərcləmək istəyir və sizdən ona kömək etməyinizi xahiş edir.
Giriş verilənləri
Birinci sətirdə iki ədəd n və m (1 ≤ n, m ≤ 100000) — şəhərlərin və yolların sayı verilir.
Növbəti sətirdə şəhərlər haqqında məlumat var — n ədəd 1 və ya 2 — müvafiq şəhərin hansı barona məxsus olduğunu göstərir.
Sonrakı m sətirdə a və b (1 ≤ a, b ≤ n, a ≠ b) cütləri verilir. Hər bir cüt a şəhərindən b şəhərinə yolun mövcudluğunu göstərir. Baytlandiya yolları ilə hər iki istiqamətdə hərəkət etmək mümkündür.
Çıxış verilənləri
Əgər axtarılan yol mövcud deyilsə, yalnız bir söz impossible yazın. Əks halda, birinci sətirdə minimal dəyəri və ziyarət edilən şəhərlərin sayını yazın, ikinci sətirdə isə bu şəhərləri ziyarət sırasına görə yazın. Əgər minimal yollar bir neçədirsə, istənilənini çıxarın.