Problem Statement
Rar the Cat is helping to build a road network so that humans can walk with dinosaurs.
There are a total of N cities and Rar the Cat has already build several roads between them. However, dinosaurs vary in height and each road has its own height limit.
A road network is considered 'safe for X m' if a dinosaur (or human or cat) can travel between any two pairs of cities without exceeding the height limits of any road in its path.
Rar the Cat wants to calculate what is the largest possible X value so he knows whether Jacq the tall T-Rex can travel safely on his road network.
Input
The first line of input will be N, the number of cities. There will not be more than 500 cities.
Subsequent N lines will contain N integers each. The jth integer of the ith row is the height limit for the road that allows dinosaurs to travel from city i to city j.
Do note that the height limits are not the same for both directions. Furthermore, some roads might be only 1-way. If the height limit is 0, it means that there is no road. It is guaranteed that there is no road from city i to city i itself.
All height limits are in metres and will not exceed 1000km
Output
The first line of output should contain only one integer, the maximum value of X such that the road network is safe for dinosaurs of Xm
If there is no indirect or direct path between any two cities within the road network, output 0 instead.
Subtasks
This problem employs an average grading scheme and has no subtasks.
Sample Input
5
0 1 2 3 4
2 0 1 3 2
5 2 0 1 3
1 1 4 0 1
1 2 3 4 0
Sample Output
2
Explanation for Sample Output
Although the direct road from city 1 to city 2 has a height limit of only 1, a dinosaur can first go to city 3 along the road with height limit 2 and then go back to city 2 along the road with height limit 2.
Therefore, the road network is also considered safe for dinosaurs ≤ 2m high