Una grilla tiene celdas de tierra (\(1\)) y de agua (\(0\)). Una isla es un grupo máximo de celdas de tierra unidas por los lados. La grilla está conectada si tiene exactamente una isla. Cada día puedes convertir una celda de tierra en agua. Encuentra la menor cantidad de días para que la grilla deje de estar conectada (si ya no lo está, la respuesta es \(0\)).

Entrada

La primera línea tiene \(R\) y \(C\) \((1 \le R, C \le 30)\). Siguen \(R\) líneas con \(C\) valores \(0\) o \(1\).

Salida

La menor cantidad de días.

Ejemplo 1

Entrada

2 4
0 1 1 0
0 1 1 0

Salida

2

Ejemplo 2

Entrada

1 2
1 1

Salida

2

Ejemplo 3

Entrada

2 2
0 0
0 0

Salida

0