Sehrli Obyekt Axtarışı#1824
Siz sehrli bir meşədə gizlədilmiş bir obyekt axtaran axtarıcısınız. Obyekt ağaclardan birinin budaqlarının arxasında, sizin görmə sahənizdən kənarda gizlədilib. Siz istənilən ağacı yoxlaya ("axtara") bilərsiniz; əgər obyekt həmin ağacdadırsa, onu dərhal tapırsınız. Əgər yoxdursa, siz axtarış aparanda obyekt sizin xəbəriniz olmadan bağlantı vasitəsilə qonşu bir ağaca keçir. Hər axtarışdan sonra o, heç vaxt eyni yerdə qalmır. Siz istənilən başlanğıc mövqeyindən və sonrakı hərəkətlərindən asılı olmayaraq obyektin tapılmasına zəmanət verən bir axtarış strategiyasının olub-olmadığını müəyyən etməlisiniz. Əgər elə bir strategiya varsa, zəmanətli uğura aparacaq ən qısa axtarış ardıcıllığını tapmalısınız.
Şəkil 2
Məsələn, tutaq ki, meşədə yalnız iki əlaqəli ağac var (Şəkil 2-nin sol tərəfi). Bu halda, eyni ağacı iki dəfə axtarmaqla mütləq tapılmağa zəmanət vermək mümkündür. Əgər obyekt ilk axtarışınızda oradadırsa, onu tapacaqsınız. Əks halda, o, digərində olmalı idi və ikinci dəfə axtaranda yerini dəyişəcək və beləliklə siz onu tapacaqsınız.
Ancaq meşənin quruluşundan asılı olaraq, bəzən uğura zəmanət vermək mümkün olmaya bilər. Belə hallardan biri üç ağacın hamısının bir-birinə bağlı olduğu vəziyyətdir (Şəkil 2-nin sağ tərəfi). İstənilən yeri axtarsanız belə, istənilən anda obyektin ola biləcəyi iki ehtimalı mövqe qalır. (Qeyd edin ki, siz obyektin hər zaman növbəti axtarış yerinizi qabaqladığı ən pis ssenariyə hazır olmalısınız.)
Giriş bir neçə testdən ibarətdir, hər biri bir boş sətirlə ayrılır. Hər test aşağıdakı kimi başlayır: bir sətrdə iki tam ədəd və (1 \leq n \leq 21); meşədəki ağacların sayıdır, isə ağaclar arasındakı qonşuluq əlaqələrinin sayıdır. Sonrakı sətrin hər birində -dən n-1-ə qədər (hər ikisi daxil olmaqla) iki müxtəlif tam ədəd göstərilib və bu, qonşu olan ağacların identifikatorlarıdır. Cütlüyün sırası əhəmiyyət kəsb etmir və eyni cütlük bir dəfədən artıq verilmir. Bundan əlavə, heç bir ağac özünə qonşu deyil və meşədə istənilən iki ağac arasında həmişə yol mövcuddur.
Testlər ardıcılığı yalnız iki sıfırdan ibarət bir sətrə çatdıqda bitir (eyni zamanda qabağında bir boş sətrlə).
Hər test üçün bir sətir çap edin. Əgər vəzifə mümkün deyilsə, sadəcə '**Impossible**' sözünü yazın. Əks halda, zəmanətli uğur üçün tələb olunan ən qısa axtarış ardıcıllığını belə formatda çap edin: **L: V_1 V_2 ... V_L**, burada ardıcıllığın uzunluğudur, V_1, V_2, \ldots, V_L isə axtarış yerlərini düzgün ardıcıllıqla göstərən və boşluqlarla ayrılmış ağac identifikatorlarıdır. Əgər bir neçə ən qısa ardıcıllıq varsa, leksikoqrafik olaraq kiçik olanını çap edin. (Bir ardıcıllıq digərindən o zaman kiçik sayılır ki, ilk fərqli elementində birincidə olan daha kiçikdir.)
Nümunə 1