e-olymp
Məsələlər

Çayı keçmək

Çayı keçmək

story2.png

Barış və Murad Bakı zooparkında heyvanlara nəzarət şöbəsində nəzarətçi işləyirlər. Onlar tez-tez kəndlinin problemindən daha çətin problemləri həll etmək məcburiyyətində qalırlar. Məsələn, bir dəfə onlar iki qayıqdan istifadə etməklə zooparkdakı bütün heyvanları Kür çayı üzərindən keçirməli idi. Özünüzü onların yerində təsəvvür edin!

Zooparkda n sayda heyvan var. Əgər bəzi heyvanlar birlikdə nəzarətsiz buraxılsa, onlardan hansısa, digər birini yeyə bilər. Hər bir heyvan üçün, onun hansı heyvanları yeyə biləcəyi bilinir. Nəzarətçilərin hər ikisi öz işində çox mahirdir və onlar hətta pələnglə belə bacararlar! Hər hansı heyvanın yanında nəzarətçilərdən ən az biri olduqda, o heç bir heyvanı yeyə bilməz.

Nəzarətçilərin iki qayığı var. Təhlükəsizlik qaydalarına görə, iki və daha çox heyvanı eyni zamanda eyni qayığa qoymaq olmaz. Hər hansı bir qayıqda eyni zamanda ən çoxu bir nəzarətçi və bir heyvan ola bilər. İlk başda bütün heyvanlar, nəzarətçilər və qayıqlar çayın sol tərəfində dayanıb. Onların hamısı çayın sağ tərəfinə keçməlidir. (Aydındır ki, çayın yalnız iki tərəfi var)

Nəzarətçilər çayın iki kənarı arasında qayıqla istədikləri kimi üzə bilərlər. Qayıqlar nəzarətçi olmadan hərəkət edə bilməz. Əgər nə vaxtsa çayın bir tərəfində biri digərini yeyə bilən heyvan cütü nəzarətsiz qalarsa, o zaman bədbəxt hadisə baş verəcək. Təbii ki, bu baş verməməlidir. Bütün heyvanlar çayın sağ tərəfinə sağ-salamat keçirilməlidir.

Sizdən bunun mümkün olub-olmadığını təyin etmək tələb olunur.

Giriş verilənləri

İlk sətirdə bir tam ədəd n (1n200) - zooparkdakı heyvanların sayı verilir. Heyvanlar 1 - n aralığında fərqli ədədlərlə nömrələnmişdir.

Növbəti n sətirdə hər bir heyvan üçün, onu yeyə biləcək heyvanların siyahısı verilir. Bunların i-cisində i nömrəli heyvan üçün, mənfi olmayan ki ədədi – onu yeyə biləcək heyvanların sayı, daha sonra isə ki sayda müxtəlif ədəd – bu heyvanların nömrələri verilir. Bu ədədlər 1 - n aralığında yerləşir və i-dən fərqlidir (heç bir heyvan özü-özünü yeyə bilməz).

Bütün ki-lərin cəmi 1500-dən çox deyil.

Çıxış verilənləri

Əgər bütün heyvanları çayın o biri tərəfinə sağ-salamat keçirmək mümkündürsə “:)”, əks halda “:(“ çap edin.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4
3 3 2 4
1 1
1 1
1 1
Çıxış verilənləri #1
:)
Giriş verilənləri #7
5
4 2 5 3 4
4 3 1 4 5
4 1 5 2 4
4 1 5 3 2
4 4 2 1 3
Çıxış verilənləri #7
:(
Müəllif Rashad Mammadov
Mənbə 2019 Azərbaycan Milli İnformatika Olimpiadası, Final Turu, May 5