Müsabiqə Zalı Hazırlığı#6530
ACM-ACPC regional müsabiqəsindən əvvəl, sayt direktoru və könüllülər müsabiqəyə hazırlıqla çox məşğul idilər. Onların vəzifələrindən biri hər bir komandaya elə bir masa təyin etmək idi ki, eyni universitetdən olan iki komanda bir-birinə bitişik olmasın. Sayt direktoru bu işə vaxt itirməmək qərarına gəldi və hakimlərdən bunu etmələrini istədi. Hakimlər düşündülər ki, bu, müsabiqə problemləri dəstində istifadə edilə biləcək yaxşı bir problem ola bilər. Müsabiqəyə hazırlıqla çox məşğul olduqları üçün hakimlər problemin bir hissəsini həll etməyə və qalanını iştirakçılardan həll etmələrini istəməyə qərar verdilər.
Hakimlər komandaların masalara təyin olunması üçün bir neçə düzülüş yaradacaq və iştirakçılardan hər bir düzülüşün etibarlı olub-olmadığını yoxlayan bir proqram yazmalarını istəyəcəklər. Əgər bir düzülüş etibarlı deyilsə, proqram ən azı iki komandası bir-birinə bitişik oturan neçə fərqli universitet olduğunu saymalıdır. "Yaxşı, siz bu həlləri gələn ilin müsabiqəsi üçün istifadə edə bilərsiniz", deyə baş hakim Əhməd Əli sayt direktoruna dedi.
Müsabiqə zalı N sətirli və hər sətirdə M hüceyrə olan 2D şəbəkə kimi təsvir edilə bilər. Şəbəkədəki hər bir hüceyrə ya bir komanda tərəfindən tutulub, ya da boşdur. Bir komandaya bitişik olan komandaların sayı 8-ə qədər ola bilər. Əgər bir komanda zalın kənarında oturubsa və ya bitişik hüceyrələrdən bəziləri boşdursa, bitişik komandaların sayı 8-dən az ola bilər.
Məsələn, aşağıdakı şəkildə göstərilən düzülüşdə, E komandası A, B, C, D, F, G və H adlanan 7 bitişik komandaya malikdir, A komandasının bitişik komandaları isə B, D və E-dir.
Proqramınız bir və ya daha çox test nümunəsi üzərində sınaqdan keçiriləcək. Girişin ilk sətri test nümunələrinin sayı olan T tək tam ədədindən ibarət olacaq (1 ≤ T ≤ 100). Test nümunələrindən sonra hər biri bir boşluqla ayrılmış N və M (1 ≤ N, M ≤ 100) tam ədədlərini ehtiva edən bir sətirlə başlayır, zalın ölçülərini təmsil edir, ardınca N sətir gəlir, hər sətir bu sıradakı masaların təyinatını təmsil edən bir boşluqla ayrılmış M tam ədədindən ibarətdir. Hər bir tam ədəd bu masaya təyin olunmuş komandanın universitet ID-sini və ya boşdursa -1-i təmsil edir. Bütün universitet ID-ləri 100-dən böyük olmayan müsbət tam ədədlərdir.
Hər bir test nümunəsi üçün, ən azı iki komandası bir-birinə bitişik oturan fərqli universitetlərin sayını təmsil edən bir tam ədəd çap edin.
Nümunə 1