Ölümcül Döyüş
Монстрların Xarici dünyadan Yer kürəsini fəth edə bilməsi üçün Ölüm Döyüşündə ardıcıl on qələbə qazanmalıdırlar. Turnirlər nəsildən-nəsilə keçirilir və Yer kürəsinin döyüşçüləri artıq doqquz məğlubiyyətə uğrayıblar. Həlledici Ölüm Döyüşünün vaxtı gəlib çatıb.
Ölüm Döyüşündə N monstr və Yerin M ən yaxşı döyüşçüsü iştirak edir. Turnirin qaydalarına görə, hər bir monstr insanlardan biri ilə döyüşməlidir (bütün monstrlar müxtəlif insanlarla). Əgər heç olmasa bir monstr qələbə qazansa, Yer kürəsi əbədi olaraq Xarici dünyanın dəhşətli imperatorunun mülkiyyətinə keçəcək. Bununla belə, insanlara rəqibləri və döyüşlərin ardıcıllığını seçmək hüququ verilir.
Yer kürəsinin himayədarı Raiden, bütün insanların rəqiblərinə qalib gəlməsi üçün döyüşçüləri seçməlidir. Yer kürəsinin hər bir döyüşçüsü üçün hansı monstrları məğlub edə biləcəyi məlumdur. Əvvəlcə, ilk döyüş üçün rəqib cütlüyü seçmək lazımdır.
Belə ki, Liu Kang Goro ilə döyüşmək istəyir, lakin o, Shang Tsung-u məğlub edə bilən yeganə döyüşçüdür, halbuki Goro digər döyüşçülər, məsələn, Johnny Cage tərəfindən məğlub edilə bilər. Buna görə də, Liu Kang və Goro arasında ilk döyüş Liu Kang-ın qələbəsi ilə nəticələnsə belə, Yer kürəsinin ələ keçirilməsinə səbəb olacaq, çünki sonra Shang Tsung rəqibinə qalib gələcək.
Raiden tərəfindən heç bir halda seçilməməli olan cütləri müəyyən edin ki, insanların azadlıqlarını qorumaq şansı qalsın.
Giriş verilənləri
Birinci sətirdə tam ədədlər N və M verilir. 1 ≤ N ≤ 300, N ≤ M ≤ 1500. Sonra N×M ölçüsündə sıfır və birlərdən ibarət A matrisi verilir. A_ij = 1, yalnız və yalnız j-ci Yer döyüşçüsü i-ci monstru məğlub edə bilirsə.
Çıxış verilənləri
N×M ölçüsündə B matrisini çıxarın. B_ij rəqib cütü (i, j) ilk döyüş üçün seçilə bilməzsə birə, əks halda sıfıra bərabər olmalıdır.