Yolun nömrələnməsi
Şəhərdəki yolayırıcıları birtərəfli yol ilə birləşdirilmişdir. Hər bir yolayırıcı cütlüyü arasındakı müxtəlif yolların sayını hesablayın. Yolayırıcılarını birləşdirən biristiqamətli yollar ardıcıllığı yol adlanır.
Yolayırıcıları mənfi olmayan tam ədədlərlə işarə olunurlar. Birsitiqamətli yol onun birləşdirdiyi yolayırıcılar cütlüyü ilə işarə edilir. Məsələn, j k onu göstərir ki, biristiqamətli yol j yolayırıcısından k yolayırıcısına gedir. Qeyd edək ki, ikisitiqamətli yol iki biristiqamətli yol ilə modelləşdirilə bilər: j k və k j.
Küçələri növbəti şəkildə birləşdirilmiş dörd yolayırıcısı olan şəhərə baxaq:
0 1
0 2
1 2
2 3
0 və 1 yolayırıcıları arasında yalnız bir, 0 və 2 arasında iki (bu 0 → 1 → 2 və 0 → 2-dir), 0 və 3 arasında iki, 1 və 2 arasında bir, 1 və 3 arasında bir, 2 və 3 arasında bir yol var, başqa yollar yoxdur.
Ola bilsin ki, bir neçə yolayırıcı arasında sonsuz sayda yollar olsun. Məsələn, əgər yuxarıda təsvir olunmuş yollar çoxluğuna 3 2 əlavə edilərsə, 0 və 1 arasında yalnız bir yol qalacaq, lakin 0 və 2 arasında sonsuz sayda yol əmələ gələcək. Ona görə ki, 2-dən 3-ə və 3-dən 2-yə geriyə sonsuz sayda müxtəlif yollarla ixtiyari sayda hərəkət etmək olar. Yəni 0 → 2 → 3 → 2 → 3 → 2 və 0 → 2 → 3 → 2 yolları müxtəlifdir.
Giriş verilənləri
İlk sətir şəhərdəki biristiqamətli küçələrin sayını və ardınca da onların təsvirini ehtiva edir. Hər bir küçə onun birləşdirdiyi yolayırıcılar cütlüyü ilə verilir: hər bir j k cütlüyü j yolayırıcısından k yolayırıcısına qədər biristiqamətli küçəni təmsil edir. Bütün şəhərlərdə yolayırıcıları ardıcıl olaraq 0-dan "ən böyüyünə" qədər nömrələnir. Giriş verilənlərində bütün tam ədədlər boşluqla ayrılmışdır.
Heç bir biristiqamətli küçə yolayırıcısından özünə yol aparmır. Heç bir şəhər 30-dan artıq yolayırıcısına malik deyil.
Çıxış verilənləri
j və k yolayırıcıları arasındakı müxtəlif yolların sayı haqqında informasiya ehtiva edən kvadrat matrisi verin. Əgər veriləcək matrisi M ilə işarə edəriksə, onda M[j][k] - j-dən k yolayırıcısına aparan müxtəlif yolların sayıdır. M matrisini sətir-sətir sətirlərin artma ardıcıllığına görə verməli.
Əgər iki yolayırıcısı arasında sonsuz sayda yol olarsa, -1 verməli. Matrisi verərkən çıxış verilənlərini tarazlaşdırmaq üçün narahat olmayın. Matrisin sətirlərindəki veriləcək bütün ədədlər bir boşluqla ayrılmalıdır.