Given a graph as an adjacency matrix, find the shortest path from the first to the last vertex.

Input Specification

~N \le 100~, the number of vertices.
The adjacency matrix - ~N~ rows of ~N~ numbers.
The first row represents the first vertex, and similarly the last row represents the last vertex.

Output Specification

The distance from the first to the last vertex.

Sample Input

3
0 1 0
0 0 1
0 0 0

Sample Output

2