\textbf{Gizli Laboratoriya}#5678
Məşhur agent 003 James Summer, dağlarda yerləşən gizli laboratoriyadan yeni superbombanı oğurlamağı planlaşdırır. Laboratoriyada bir neçə otaq var və bu otaqlar qapılarla birləşdirilib. Hər bir qapını laboratoriyada çalışan bəzi tədqiqatçılar öz elektron açarları ilə aça bilərlər.
James bəzi tədqiqatçıları öldürərək onların açarlarını ələ keçirə bilər. Bu halda, o, həmin tədqiqatçıların aça bildiyi bütün qapıları aça bilər. Həmçinin, o, qapının yanında gözləyərək, kimsə keçəndə onunla birlikdə keçə bilər. Agentlər laboratoriyanın gündəlik rejimini araşdırıblar, buna görə də hər bir tədqiqatçının qapılardan nə vaxt keçəcəyi məlumdur.
Kimsəni öldürdükdə, James öz missiyasının uğursuzluq riskini artırır. Həmçinin, laboratoriya ərazisində qaldığı hər saniyə risk artır. Beləliklə, James hansı tədqiqatçıların açarlarını götürməli olduğunu və superbombanın yerləşdiyi otağa necə gedib çıxacağını və oradan necə çıxacağını seçməlidir ki, missiyanın uğursuzluq riski minimum olsun.
Giriş faylının ilk sətrində laboratoriyadakı otaqların sayı n, qapıların sayı m və tədqiqatçıların sayı k verilir (2 \le n \le 20, 1 \le m \le 100, 1 \le k \le 10). Sonra m sətir qapıların təsvirini ehtiva edir — hər bir qapı onun birləşdirdiyi otaqların nömrələri ilə təsvir edilir. Bütün qapılar iki tərəflidir və hər iki tərəfdən açılır. İki otaq bir neçə qapı ilə birləşdirilə bilər.
Daha sonra tədqiqatçıları təsvir edən k blok verilir. Hər blok bu tədqiqatçını öldürdükdə James-in aldığı riskin tam ədədi r_i ilə başlayır (1 \le r_i \le 32000). Sonra bu tədqiqatçının aça bildiyi qapıların sayı d_i və qapıların siyahısı verilir. Qapılar faylda verildiyi kimi 1-dən başlayaraq nömrələnir. Tədqiqatçının gündəlik rejimi davam edir. Bu, onun gündəlik açdığı qapıların sayı a_i ilə başlayır, sonra isə a_i cüt tam ədədlər — tədqiqatçının açdığı qapının nömrəsi və iş gününün başlanğıcından etibarən saniyə ilə ölçülən vaxt verilir (bu vaxt müsbətdir və iş gününün uzunluğunu keçmir, yəni saat və ya saniyə). Hadisələr xronoloji ardıcıllıqla verilmişdir, a_i \le 10. Hər bir tədqiqatçının yalnız öz elektron açarı ilə aça bildiyi qapılardan keçdiyi təmin edilir.
James öz missiyasına iş günü ərzində istənilən vaxt başlaya bilər və missiyası iş gününün sonuna qədər başa çatmalıdır. Laboratoriyada qaldığı hər saniyə onun riski 1 artır. James laboratoriyaya girişdə, yəni otaq nömrəsi 1-də başlayır. Superbomba otaq nömrəsi n-də yerləşir. James superbombanın olduğu otağa gedib çıxmalı və laboratoriya girişinə qayıtmalıdır. James-in iki qapıdan keçməsi üçün ən azı bir saniyə lazım olduğunu nəzərə almalısınız, xüsusən də ilk qapıdan keçməsi üçün ən azı bir saniyə lazımdır. Onun missiyası superbomba ilə laboratoriya girişinə girdikdən bir saniyə sonra başa çatır.
Əgər missiyanı yerinə yetirmək mümkün deyilsə, çıxış faylının ilk sətrində "mission impossible" yazdırın. Əks halda, missiyanı yerinə yetirmək üçün James-in almalı olduğu minimal riski yazdırın.
Bundan sonra James-in izləməli olduğu planı yazdırın. Əvvəlcə öldürülməli olan tədqiqatçıların sayını və onların nömrələrini yazdırın. Sonra James-in laboratoriyaya girməli olduğu vaxtı iş gününün başlanğıcından etibarən yazdırın. Bu, James-in keçdiyi qapıların siyahısı ilə davam etməlidir, hər biri James-in keçdiyi vaxtla birlikdə, iş gününün başlanğıcından etibarən ölçülən saniyələrlə. Sonuncu rəqəm James-in missiyasının başa çatdığı vaxt olmalıdır.
Nümunə 1