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