Ulduz yolları
Kosmik səyahətçilər ulduz qapıları arasında yollar haqqında informasiya tapdılar. Ondan istifadə edərək kosmik hipertunellə digər dünyaya düşmək olar. Müxtəlif dünyalar arasında olan ulduzlar arası yollar matris şəklindədir. Bütün qapılar nömrəyə malikdir (1 ≤ i ≤100). Yollar matrisinin(i,j) mövqeyində əgər (i)-ci ulduzdan (j)-cu ulduza düz yol varsa, 1 yerləşir.
Qalan mövqelərdə isə 0(sıfır) yerləşir. (i)-ci ulduzdan (j)-cu ulduza düz yolun olması (j)-cu ulduzdan (i)-ci ulduza belə yolun olmasına təminat verilmir. Lakin həmişə (i,i) mövqelərində 1 var.
Tapşırıq aşağıdakılardan ibarətdir. Siz verilmiş matris üzrə yollara əsasən bütün mümkün yolları göstərən irəlilədilmiş yolların matrisini tapmalısınız. Bu matris hər bir digər (i)-ci ulduzdan (k)-cı ulduza getməyin mümkün olub-olmaması haqqında informasiya verməlidir. Başqa sözlə, (i)-ci ulduzdan (j)-cu ulduza və (j)-cu ulduzdan da (k)-cı ulduza yol varsa, onda (i)-ci ulduzdan (k)-cu ulduza da yol var. Yolların mümkün olması matrisin uyğun mövqeyindəki 1 ədədi vasitəsilə təsvir olunur.
Beləliklə, irəlilədilmiş yollar yalnız düz xətt boyunca olmaya da bilər, aralıq qapılar da yerləşə bilər.
Giriş verilənləri
Birinci sətirdə matrisin M (M ≤ 100) ölçüsü, sonrakı sətirlərdə matrisin sətirləri yerləşir. Sətirlərdə elementlər aralarında bir boşluq işarəsi olmaqla ayrılır. Giriş verilənləri korrektdir.
Çıxış verilənləri
Çıxış-bu irəlilədilmiş yollar matrisinin sətirbəsətir yazılışıdır, elementlər bir boşluq işarəsi ilə ayrılır.