Tullan meymun
Siz meşədə bir meymunu təqib edən ovçusunuz və onu hər şeyə qadir avtomat tüfənginizlə vurmağa çalışırsınız. Meymun ağaclardan birinin budaqlarının arxasında, gözünüzdən uzaqda gizlənir. Siz ağaclardan birini nişan alıb ata bilərsiniz; güllələriniz budaqlardan keçərək meymunu dərhal öldürə bilər, əgər o həmin ağacda olarsa. Əgər olmasa, meymun sizin yenidən doldurmağınıza sərf etdiyiniz vaxtdan istifadə edərək, sizin xəbəriniz olmadan qonşu ağaca sıçrayır. O, heç vaxt atışdan sonra eyni yerdə qalmır. Meymunu ilk yerləşdiyi yer və sonrakı sıçrayışlarından asılı olmayaraq tutmağa imkan verən bir strategiyanın olub-olmadığını öyrənmək istəyirsiniz. Əgər belədirsə, bunu təmin edən ən qısa atış ardıcıllığını müəyyən etməlisiniz.
Şəkil 2
Məsələn, meşədə yalnız iki qonşu ağacın olduğu vəziyyəti nəzərdən keçirin (Şəkil 2-nin sol tərəfi). O zaman eyni ağaca iki dəfə atəş açaraq meymunu tutmağınıza əmin olmaq mümkündür. İlk atışınız meymun ilk növbədə orada olsaydı uğurlu olur. Əks halda, meymun digər ağacın arxasında idi və siz ikinci dəfə atəş açdığınız zaman mütləq hərəkət edəcək.
Lakin, meşənin formasından asılı olaraq, qələbəni təmin etmək mümkün olmaya bilər. Bunun bir nümunəsi, üç ağacın hamısının bir-birinə bağlı olduğu vəziyyətdir (Şəkil 2-nin sağ tərəfi). Haraya nişan alsanız da, hər an meymun üçün həmişə iki mümkün yer var. (Burada meymunun növbəti hədəf ağacınızı ardıcıl olaraq təxmin edə biləcəyi ən pis vəziyyətlə maraqlanırıq).
Giriş verilənləri
Giriş bir neçə test halından ibarətdir, hər biri boş sətirlə ayrılır. Hər test halı iki tam ədəd n və m (1 ≤ n ≤ 21) olan bir sətirlə başlayır; n meşədəki ağacların sayıdır və m ağaclar arasındakı qonşuluq əlaqələrinin sayıdır. Növbəti m sətirin hər biri 0 və n-1 (daxil olmaqla) arasında iki fərqli tam ədəd ehtiva edir, qonşu cütün ağaclarının identifikatorları. Cüt içindəki ağacların sırası heç bir məna daşımır və heç bir cüt bir dəfədən çox görünmür. Siz daha da fərz edə bilərsiniz ki, heç bir ağac özünə qonşu deyil və meşədəki hər hansı iki ağac arasında həmişə bir yol var.
Test halları yalnız iki sıfırdan ibarət bir sətirlə bitəcək (həmçinin boş sətirlə əvvəlcədən).
Çıxış verilənləri
Hər test halı üçün bir sətir çap edin. Əgər tapşırıq mümkün deyilsə, sətir 'Impossible' sözünü ehtiva etməlidir. Əks halda, tələb olunan xüsusiyyətə malik ən qısa atış ardıcıllığını L: V_1V_2...V_L formatında ehtiva etməlidir, burada L ardıcıllığın uzunluğudur və V_1, V_2,..., V_L düzgün sırada atəş açılacaq ağacların identifikatorlarını ehtiva edən boşluqla ayrılmış tam ədədlərdir. Əgər bir neçə ən qısa ardıcıllıq varsa, leksikoqrafik olaraq ən kiçiyini çap edin. (Bir ardıcıllıq digərindən leksikoqrafik olaraq kiçikdir, əgər fərqləndikləri ilk element birincidə kiçikdirsə).