B. Тайная комната
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

«Тайная комната снова открыта» — эта новость распространилась по всему Хогвартсу. Дамблдор был уволен и теперь Гарри пытается попасть в тайную комнату. Лорд Волдеморт не доволен таким развитием событий, он хочет помешать Гарри.

Тайная комната представляет собой прямоугольное поле n × m, в некоторых клетках которого стоят колонны. Колонны обладают необычным свойством: луч света может беспрепятственно проходить сквозь них, не меняя своего направления. Используя магию, можно превратить некоторые колонны в магические. Магические колонны отличаются от обычных тем, что луч света, проходящий через магическую колонну, отражается в четыре стороны как показано на рисунке.

Слева свет проходит через обычную колонну, справа — через магическую.

Василиск находится на правой стороне правой нижней клетки поля и смотрит налево (в сторону левой нижней клетки). Как гласит легенда, тот, кто посмотрит прямо в глаза Василиску, сразу умирает. А тот, кто посмотрит в глаза Василиску через колонну, окаменеет. Мы знаем, что дверь в тайную комнату находится на левой стороне левой верхней клетки поля, а также что любой заходящий в комнату человек обязательно будет смотреть по направлению своего движения (то есть в сторону правой верхней клетки).

На рисунке изображен первый тестовый пример.

Вам заданы размеры тайной комнаты и позиции колонн. Лорд Волдеморт попросил вас найти минимальное количество колонн, которое нужно сделать магическими, чтобы любой, кто вошел в тайную комнату, немедленно окаменел, или сказать, что задуманное сделать невозможно.

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

В первой строке записано два целых числа n и m (2 ≤ n, m ≤ 1000) — размеры тайной комнаты. Следующие n строк содержат по m символов. Каждый символ равен «.» или «#» и описывает соответствующую клетку тайной комнаты. Символ равен «.» — если соответствующая клетка комнаты пустая, «#» — если соответствующая клетка содержит обычную колонну.

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

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

Примеры
Входные данные
3 3
.#.
...
.#.
Выходные данные
2
Входные данные
4 3
##.
...
.#.
.#.
Выходные данные
2
Примечание

На картинке выше показан первый тестовый пример. Обе колонны в первом примере нужно сделать магическими. Значком дракона обозначен Василиск, значком бинокля обозначен наблюдатель, который войдет в тайную комнату. Черная звездочка обозначает место, где должно произойти окаменение. Желтыми линиями обозначается движение света через колонны.