Sızma#3391
Günaydın, agent W-12. Missiyanız, qəbul etməyi seçsəniz, aşağıdakı kimidir.
Biz, Xaos və Şər Birliyinin (ACM) komanda strukturunu dağıtmaq üçün onların sıralarına sızmalıyıq. Təəssüf ki, onlar belə bir ehtimala hazır görünürlər və komanda strukturlarına bizim sızmamızı olduqca çətinləşdirən mürəkkəb bir dizayn qurublar.
ACM komanda strukturu bir neçə hücrəyə bölünmüşdür. Hər bir hücrə cütü A və B üçün, ya A B-ni idarə edir, ya da B A-nı idarə edir. Lakin bu "idarəetmə" əlaqəsi dövri ola bilər, belə ki, A B-ni, B C-ni və C A-nı idarə edə bilər.
Biz istənilən xüsusi hücrəyə agentlər göndərə bilərik, bu da bizə həmin hücrəni və onun idarə etdiyi hücrələri idarə etmə imkanı verir, lakin digər hücrələri yox. Yuxarıdakı nümunədə, A-ya sızmaq bizə A və B-ni idarə etmə imkanı verərdi, lakin C-ni yox.
ACM-in uğurlu sızması üçün biz onun bütün hücrələrini idarə etməliyik, əks halda bizim idarəmizdən kənarda qalan hücrələr bizi aşkar edəcək və onların məşhur xaos və şərini başlatmağa başlayacaqlar. Bildiyiniz kimi, bu günlərdə yuxarı rəhbərlikdən sərt maliyyə məhdudiyyətləri altındayıq, buna görə də bu missiyanı mümkün qədər səmərəli şəkildə yerinə yetirməliyik. Missiyanız, uğur qazanmaq üçün minimum neçə hücrəni sızmamız lazım olduğunu müəyyən etməkdir.
Bu missiya məlumatı beş saat ərzində öz-özünə məhv olacaq. Uğurlar!
Test halının ilk sətri ACM-in hücrələrinin sayı n (1 ≤ n ≤ 75) ilə başlayır. Növbəti n sətrin hər biri uzunluğu n olan ikilik bir sətir ehtiva edir, burada j-ci sətrin i-ci xarakteri hücrə j hücrə i-ni idarə edirsə 1, əks halda 0 olur (1 ≤ i, j ≤ n).
i-ci sətrin i-ci xarakteri 0 olur və i ≠ j üçün ya j-ci sətrin i-ci xarakteri 1, ya da i-ci sətrin j-ci xarakteri 1 olur, lakin hər ikisi deyil.
Hər bir test halı üçün, onun hal nömrəsini və ACM-in tam idarəsini əldə etmək üçün sızılması lazım olan minimum hücrə sayı m-i göstərin. Sonra m ədəd c_1, ..., c_m istənilən sırada göstərin, sızılması lazım olan hücrələrin siyahısını göstərərək (hücrələr 1 ilə n arasında nömrələnir). Əgər m hücrə dəstindən bir neçəsi tam idarə verirsə, istənilən biri qəbul ediləcək.
Nümunə 1