eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Флойд

Флойд

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Задано орієнтований зважений граф. Знайдіть пару вершин, найкоротша відстань від однієї з яких до іншої максимальна серед усіх пар вершин.

Вхідні дані

У першому рядку міститься кількість вершин графа n~(1 \le n \le 100). У наступних n рядках задано по n чисел, що описують вагову матрицю графа. В ній -1 означає відсутність ребра між вершинами, а довільне невід'ємне число — наявність ребра заданої ваги. На головній діагоналі матриці завжди розташовані нулі.

Вихідні дані

Виведіть шукану максимальну найкоротшу відстань.

Приклад

Вхідні дані #1
4
0 5 9 -1
-1 0 2 8
-1 -1 0 7
4 -1 -1 0
Вихідні дані #1
16