# Shortest Bridge

easy

In a given 2D binary array grid, there are two islands. Now, we may change 0s to 1s so as to connect the two islands together to form 1 island. Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

## Constraints

1<= n <= 1000

## Format

### Input

First line contains an integer n. Each of next n lines contain n numbers containing either 0 or 1.

### Output

Return the smallest number of 0s that must be flipped.

## Example

Sample Input

3
0 1 0
0 0 0
1 1 1

### Sample Output

1