Железная крепость представляет собой прямоугольную сеть помещений размером n × m. В каждом помещении может находиться:

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

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

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

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

В первой строке даны два целых числа n и m — количество строк и столбцов в плане крепости.

В следующих n строках содержится по m целых чисел a[i][j] (0, 1 или 2) — описание помещений крепости.

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

Выведите одно целое число:

• минимальное количество минут, необходимое для поднятия тревоги во всех помещениях с гарнизоном;
• -1, если это невозможно.

Ограничения

• 1 ≤ n, m ≤ 100
• a[i][j] ∈ {0, 1, 2}

Примеры

Пример 1

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

3 3
2 1 1
1 1 0
0 1 1

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

4

Пример 2

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

3 3
2 1 1
0 1 1
1 0 1

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

-1

Пример 3

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

1 2
0 2

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

0