Условие:
Дан связный взвешенный неориентированный граф.
Рассмотрим пару вершин, расстояние между которыми максимально среди всех пар вершин. Расстояние между ними называется диаметром графа. Эксцентриситетом вершины v называется максимальное расстояние от вершины v до других вершин графа. Радиусом графа называется наименьший из эксцентриситетов вершин. Найдите диаметр и радиус графа.
Формат ввода
В первой строке входного файла единственное число: \nN
(
1
≤\nN
≤
1
0
0
) — количество вершин графа. В следующих \nN
строках по \nN
чисел — матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда нули; веса рёбер не превышают 1000.
Формат вывода
В выходной файл выведите два числа — диаметр и радиус графа.
