28718번 - Защитный узор 스페셜 저지다국어

Беверли прочитала в старой книге, которую нашла в библиотеке, что некоторые узоры могут отпугивать злые силы. Теперь она хочет нарисовать специальный узор на своей входной двери, чтобы временно отпугнуть Пеннивайза.

Входная дверь Беверли представляет собой клетчатый прямоугольник размера $n \times m$. Каждая клетка прямоугольника покрашена в белый или черный цвет. Беверли считает, что узор на двери будет отпугивать Пенивайза, если:

• На двери будет хотя бы одна черная клетка
• Если соединить ребрами соседние по стороне черные клетки, в этом графе:
  • Будет одна компонента связности
  • Не будет существовать простого цикла

Беверли может перекрасить некоторые клетки на двери, при перекрашивании цвет клетки изменяется с белого на черный, и наоборот. При этом, она хочет закончить как можно быстрее, а поэтому хочет минимизировать количество перекрашиваний. Помогите ей найти любой узор, удовлетворяющий требуемым ограничениям, и требующий минимального возможного количества перекрашиваний клеток. Конечно же, Беверли будет перекрашивать каждую клетку не более одного раза.

В первой строке даны два целых числа $n$ и $m$ --- высота и ширина двери ($1 \le n \le 100$, $1 \le m \le 10$). В следующих $n$ строках дано по $m$ символов <<.>> и <<#>> --- описание исходного узора на двери. Символ <<.>> соответствует белому цвету, а <<#>> --- черному.

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

В первом тесте Беверли потребуется перекрасить минимум одну клетку.

Во втором тесте Беверли потребуется перекрасить минимум две клетки.

В третьем тесте Беверли потребуется перекрасить минимум одну клетку.