Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин (при этом возможно, что между какими-то вершинами пути нет совсем - нужно выбрать наибольший путь из тех пар вершин, между которыми пути существуют).
Формат входных данных
В первой строке входного файла единственное число N (1 <= N <= 100) -
количество вершин графа. В следующих N строках по N чисел -
матрица смежности графа, где -1 означает отсутствие ребра между
вершинами, а любое неотрицательное число - присутствие
ребра данного веса. На главной диагонали матрицы - всегда нули.
Формат выходных данных
Вывести искомое максимальное кратчайшее расстояние.
Пример
| Пример ввода | Пример вывода |
4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0 |
16 |