e-olymp
Соревнования

Azerbaijan Programming Olympiad - 2nd Stage preparation

Диаметр графа

Дан связный взвешенный неориентированный граф.

Рассмотрим пару вершин, расстояние между которыми максимально среди всех пар вершин. Расстояние между ними называется диаметром графа. Эксцентриситетом вершиныv называется максимальное расстояние от вершины v до других вершин графа. Радиусом графа называется наименьший из эксцентриситетов вершин.

Найдите диаметр и радиус графа.

Входные данные

В первой строке находится количество вершин графа n (1n100). В следующих n строках по n чисел - матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. На главной диагонали матрицы всегда нули; веса рёбер не превышают 1000.

Выходные данные

Выведите два числа: диаметр и радиус графа.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4
0 -1 1 2
-1 0 -1 5
1 -1 0 4
2 5 4 0
Выходные данные #1
8
5