Floyd – yaşama

İstiqamətlənmiş çəkili qraf verilir. Onun əlaqəlilik matrisinə görə hər bir təpələr cütlüyü üçün onlar arasında ən qisa yolun olub olmamasını təyin etmək lazımdır.

Ən qısa yol iki halda olmaya bilər:

• Heç bir yol yoxdur.

• Kiçik çəkili istənilən sayda yol var.

Giriş verilənləri

İlk sətirdə qrafın təpələrinin $n(1\le n\le 100)$ sayı verilir. Qrafın qonşuluq matrisini əks etdirən növbəti $n$ sətrin hər birində $n$ ədəd verilir ($i$ sətrinin $j$-ci ədədi $i$ təpəsindən $j$ təpəsinə tilin çəkisinə uyğundur). Ondakı $0$ ədədi tilin olmadığına işarə edir, istənilən digər ədəd isə uyğun çəkili tilin olduğuna işarə edir. Bütün ədədlər modulca $100$-ü aşmır.

Çıxış verilənləri

$n$ ədəd ehtiva edən $n$ sətir verin: $i$ sətrinin $j$-ci ədədi $i$-dən $j$-ə yol olmazsa, $0$, ən qısa yol olarsa, $1$, kiçik çəkili istənilən sayda yol olarsa, $2$ verin.

Nümunələr