Qıfıllar və açarlar
Sehrbaz V otaq və V - 1 qapıdan ibarət bir labirintdədir. Hər qapı iki otağı hər iki istiqamətdə birləşdirir. Hər hansı iki otaq arasında həmişə müəyyən bir qapı ardıcıllığı ilə keçən bir yol var. Labirintdə C kilid və C fərqli rəngdə qapıları açmaq üçün açarlar mövcuddur (hər açarın öz rəngi var); hər qapıda ən çox bir kilid var və hər otaqda ən çox bir açar var. Sehrbaz kilidlərdən keçməkdə çətinlik çəkmir, lakin o, sehrli kitabını unudub və onsuz sehrləri işləmir. Hal-hazırda sehrbaz X otağındadır və Y otağında olan sehrli kitabına ən qısa zamanda çatmaq istəyir. Hər addımda sehrbaz qonşu otağa qapıdan keçə bilər. Əgər qapı kilidlidirsə, sehrbazın həmin kilidin rəngində açarı olmalıdır (əgər bu qapı əvvəldən açılmamışdırsa). Sehrbaz yalnız bir açar daşıya bilər. Açarı götürdükdən sonra onu labirintdə bir yerdə qoyub sonra yenidən götürə bilməz. Qapı açıldıqdan sonra açar atılır, çünki artıq lazım deyil.
Verilmiş labirint və C açarların və C kilidlərin yerlərinə əsasən, X-dən Y-ə necə çatmaq olar, əgər bu mümkündürsə, müəyyən edin. Uzunluğu 4^{ . }(C + 1)^{ . }V-dən çox olmayan hər hansı bir yol qəbul ediləndir.
Giriş verilənləri
Hər testin ilk sətiri dörd tam ədədi ehtiva edir: labirintdəki otaqların sayı V (1 ≤ V ≤ 1500), kilidlərin sayı C (0 ≤ C < V), və otaqların nömrələri X və Y. Otaqlar 0, 1,..., V - 1 ədədləri ilə nömrələnmişdir. Sonra (mümkün boş) bir sətir C tam ədəd ehtiva edir, hər bir açarın yerini rənglərin artan sırasına görə təsvir edir. Növbəti V - 1 sətir labirinti təsvir edir: hər sətir üç tam ədəd A B L ehtiva edir, bu, A və B otaqları arasında L rəngində açarla açılan bir qapının olduğunu göstərir, əgər 0 ≤ L < C; L üçün -1 dəyəri qapının kilidsiz olduğunu bildirir.
Sonuncu sətir V, C, X, Y = 0, 0, 0, 0 ehtiva edir və işlənmir.
Çıxış verilənləri
Hər test üçün çıxış ayrı bir sətirdə verilməlidir. Əgər həll yoxdur, "Impossible" yazın. Əks halda, yolu L: V_0,...,V_L formatında verin, burada L ≤ 4(C + 1)V X-dən Y-ə olan yolun uzunluğudur və X = V_0, V_1,..., V_L_{-1}, V_L = Y ardıcıllığı L + 1 zirvələrdən ibarətdir, verilmiş ardıcıllıqla ziyarət edilir. Çıxış yolunda hər zirvədən əvvəl bir boşluq yazılmalıdır.