Iceberg

Because of global warming, an Arctic iceberg is melting. Represent the iceberg's heights with an N x M two-dimensional array. A cell containing part of the iceberg stores a positive integer height, and a sea cell stores 0. Blank cells in the figures should be read as 0.

Figure 1. Iceberg heights stored in a 5-row, 7-column array

The more sides of an iceberg cell touch the sea, the faster that cell melts. Each year, the height of every iceberg cell decreases by the number of adjacent 0 cells among its north, south, west, and east neighbors. A height never becomes negative. A 0 cell enclosed by iceberg cells like a lake is still considered sea. All decreases for a year are computed simultaneously from the array at the start of that year. After one year, the iceberg in Figure 1 becomes Figure 2.

Figure 2

Figure 3 shows the same iceberg after two years. In the array, iceberg cells adjacent in the north, south, west, or east direction are connected. The iceberg in Figure 2 is one connected component, while the iceberg in Figure 3 has split into three components.

Figure 3

Initially, the iceberg is one connected component. Write a program that finds the first time, in years, when it splits into at least two components. For Figure 1, the answer is 2. If the iceberg melts completely before ever splitting, output 0.

The first line contains two integers N and M, the number of rows and columns, separated by a space. Each of N and M is between 3 and 300, inclusive.

Each of the next N lines contains M integers separated by spaces, describing one row of the array. Each value is between 0 and 10, inclusive. The number of cells with height at least 1 is at most 10,000. The first and last rows, and the first and last columns, are always filled with 0.

Print the first time, in years, when the iceberg splits into at least two components. If it never splits before melting completely, print 0.