Deliver Package in a Grid City

You are given an N × N grid representing a city's intersections. Each cell in the grid contains either a 0 (passable intersection) or a 1 (restricted intersection). The task is to calculate the minimum number of intersections (including the start and end) that must be traversed to go from the top-left intersection (cell (1,1)) to the bottom-right intersection (cell (N,N)). If no such path exists, output -1.

The problem can be formulated as finding the shortest path in an unweighted grid graph. In mathematical form, if we denote by \(d(u,v)\) the minimum number of intersections on the path from vertex \(u\) to vertex \(v\), then the answer is:

[ d = \min{\text{number of intersections from } (1,1) \text{ to } (N,N)} ]

If no valid path exists, the answer is \(-1\).

inputFormat

The first line of input contains an integer N representing the size of the grid. The following N lines each contain N integers (each either 0 or 1) separated by spaces, representing the grid.

Example:

5
0 0 0 1 0
0 1 0 1 0
0 0 0 0 0
1 0 1 1 0
0 0 0 1 0

outputFormat

Output a single integer representing the minimum number of intersections that must be passed through, including the starting and ending intersections. If it is impossible to reach the destination, output -1.

Example Output:

9

## sample

5
0 0 0 1 0
0 1 0 1 0
0 0 0 0 0
1 0 1 1 0
0 0 0 1 0

9

</p>