Building a Bridge

A country is made of several islands. Its map is given as an N x N grid, where each cell is either sea or land. An island is one connected component of land cells connected vertically or horizontally.

You want to connect two different islands with one bridge. A bridge may be built only on sea cells, and its length is the number of grid cells occupied by the bridge.

Given the map, find the minimum possible length of a bridge that connects two different islands.

The first line contains the map size N. N is a natural number no greater than 100.

Each of the next N lines contains N integers separated by spaces. 0 represents sea, and 1 represents land.

The given map always contains at least two islands.

Print the minimum length of a bridge that connects two different islands.