Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8825

Jo'natishlar soni: 714634

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1179

So'ngi izohlar

763. Diameter of the graph
Vaqt limiti: 1 sekund
Xotira limiti: 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