Флойд

Verilmiş istiqamətli çəkili qrafda elə bir zirvə cütü tapın ki, bu cütlərdən birindən digərinə olan ən qısa məsafə bütün zirvə cütləri arasında maksimal olsun.

Giriş verilənləri

Birinci sətirdə qrafın zirvələrinin sayı $n(1\le n\le 100)$ verilir. Sonrakı $n$ sətirdə qrafın çəki matrisini təsvir edən $n$ ədəd verilir. Burada $-1$ zirvələr arasında kənarın olmadığını, istənilən qeyri-mənfi ədəd isə verilmiş çəkiyə malik kənarın olduğunu göstərir. Matrisin əsas diaqonalında həmişə sıfırlar yerləşir.

Çıxış verilənləri

Axtarılan maksimal ən qısa məsafəni çıxarın.

Nümunələr