Железная крепость состоит из прямоугольной сетки залов размером m x n.

В каждом зале может находиться:

• 0 — пустой зал;
• 1 — спокойный гарнизон;
• 2 — зал, где уже поднята тревога.

Каждую минуту тревога из любого зала, где она уже поднята, распространяется на все соседние по стороне залы со спокойным гарнизоном.

Требуется определить минимальное количество минут, за которое тревога охватит весь гарнизон крепости. Если существуют залы со спокойным гарнизоном, до которых тревога никогда не дойдет, выведите -1.

Входные данные

На вход подаются:

• два целых числа m и n — количество строк и столбцов сетки;
• затем m строк, в каждой из которых записано n целых чисел 0, 1 или 2 — описание крепости.

Все данные считываются из стандартного ввода.

Выходные данные

Выведите одно целое число — минимальное количество минут, необходимое для поднятия тревоги во всех достижимых залах с гарнизоном, либо -1, если охватить тревогой весь гарнизон невозможно.

Результат выведите в стандартный вывод.

Ограничения

• 1 <= m, n <= 10
• grid[i][j] равно 0, 1 или 2

Примеры

Пример 1

Входные данные

1 10
0 0 0 0 0 0 0 0 0 0

Выходные данные

0

Пример 2

Входные данные

1 10
1 1 1 1 1 2 1 1 1 1

Выходные данные

5