Avtobus marşrutları

Yeni Mikolayev şəhərətrafı ərazisində bütün yollar düzbucaqlı şəkildə yerləşir və ya cənubdan şimala, ya da qərbdən şərqə doğru uzanır. Bu səbəbdən, yollar ya bir-birinə paralel, ya da perpendikulyar olub, kəsişmələrdə birləşir. Şəhərətrafında ümumilikdə N üfüqi və M şaquli yol mövcuddur ki, bu da N*M kəsişmə nöqtəsi deməkdir.

Hazırda şəhərətrafı üçün avtobus marşrutlarının sxemi hazırlanır. Bütün marşrutlar xəritənin sol alt küncündə yerləşən kəsişmədən başlayaraq sağ üst küncündə yerləşən kəsişmədə bitməlidir. Bundan əlavə, avtobuslar ən qısa marşrutla, yəni həmişə şimala və ya şərqə doğru hərəkət etməlidir (lakin yol boyu hər hansı bir kəsişmədə avtobus istiqamətini şimaldan şərqə və ya əksinə dəyişə bilər). Bəzi kəsişmələr vacibdir: onlar sıx məskunlaşmış ərazilərin yaxınlığında yerləşir və bu kəsişmələrdən mütləq ən azı bir avtobus marşrutu keçməlidir.

Tapşırıq

Sizin vəzifəniz marşrutlar şəbəkəsini elə planlaşdırmaqdır ki, hər bir vacib kəsişmədən ən azı bir marşrut keçsin, lakin ümumi marşrutların sayı mümkün qədər az olsun.

Giriş məlumatları

busways.in giriş faylının birinci sətirində şəhərətrafında üfüqi yolların sayı N və şaquli yolların sayı M olan iki təbii ədəd var. Məlumdur ki, 2 ≤ N ≤ M ≤ 1000. Növbəti N sətirdə M kəsişmə verilir: 1 rəqəmi müvafiq kəsişmənin vacib olduğunu, 0 rəqəmi isə həmin kəsişmənin vacib olmadığını göstərir.

Çıxış məlumatları

busways.out çıxış faylı tək bir tam ədəd - sol alt kəsişmədən sağ üst kəsişməyə qədər ən qısa yollar boyunca buraxıla biləcək minimum marşrutların sayını göstərən qeyri-mənfi tam ədəd olmalıdır ki, bu marşrutlar bütün vacib kəsişmələri əhatə etsin.

Nümunələr

Qiymətləndirmə