###### Category

###### Similar Problems

## 0763. Diameter of the graph

###### Time limit : 1000 ms

Memory limit : 64 mb

Given a connected weighted undirected graph.

Consider a pair of vertices, the distance between which is maximum among all pairs of vertices. The distance between them is called the diameter of the graph. Eccentricity of vertex v is the maximum distance from a vertex v to the other vertices of the graph. Radius of a graph is the smallest of the eccentricities of the vertices.

Find the
diameter and radius of the graph.** **

**Input**

The first line of
the input only number: N (1 ≤ N ≤ 100) - the number of vertices. The next N lines by N numbers - the adjacency matrix of the graph,
where -1 means no edges between vertices, and any non-negative number - the
presence of an edge weight. On the main diagonal of the matrix is always
zero; weight edges do not exceed 1000.**
**

**Output**

Output two numbers - the diameter and radius of the graph in separate lines.

Samples

№ |
Input |
Output |

1 |
4 0 -1 1 2 -1 0 -1 5 1 -1 0 4 2 5 4 0 |
8 5 |

Text from: e-olimp.com