## 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

Tayyorladi: Azat Yusupov
Text from: e-olimp.com