406350: GYM102386 G Уральские блинчики

G. Уральские блинчикиограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

После квалификационного тура довольные, но голодные программисты зашли в ресторан «Уральские блинчики» и заказали себе несколько фирменных блинчиков. Для того чтобы приготовить блинчик, повар должен прожарить каждую из его сторон на сковороде.

Фирменный блинчик имеет форму квадрата со стороной $$$1$$$. Сковорода повара имеет форму прямоугольника ширины $$$m$$$ и высоты $$$n$$$. Она разбита на $$$n \cdot m$$$ клеток. К сожалению, некоторые из клеток подгорели, и в них нельзя класть блинчики. При этом не подгоревшие клетки образуют связную область, то есть из любой не подгоревшей клетки можно попасть в любую другую, перемещаясь каждый раз в соседнюю неподгоревшую клетку. Соседними называются такие две клетки, что либо они находятся в одной и той же строке и в соседних столбцах, либо в одном и том же столбце и в соседних строках.

В некоторые из не подгоревших клеток повар положил блинчики (не более одного на клетку), и они уже поджарились с одной стороны. Теперь их нужно перевернуть на другую сторону. Для этого можно поддеть любой блинчик лопаткой снизу и перевернуть его, переместив при этом на соседнюю клетку. Перемещать блинчики за пределы сковороды нельзя. Естественно, если перевернуть блинчик дважды, он снова будет расположен прожаренной стороной вниз. Если переместить блинчик на клетку, где уже лежит другой блинчик, они образуют стопку. Одновременно на одной из клеток могут находится сколько угодно блинчиков, но переворачивать можно только верхний из них.

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

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

В первой строке через пробел даны целые числа $$$n$$$ и $$$m$$$ — размер сковороды ($$$1 \le n, m \le 100$$$).

Далее даны $$$n$$$ строк длины $$$m$$$ каждая, описывающих сковороду. Строки состоят из символов «.» (код $$$46$$$), «#» (код $$$35$$$) и «P» (код $$$80$$$). Символ «.» обозначает, что клетка свободна; символ «#» обозначает, что клетка подгоревшая; символ «P» обозначает, что клетка занята блинчиком.

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

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

Если повар сможет перевернуть все блинчики на неподжаренную сторону, следуя условиям задачи, в единственной строке выведите «YES» (без кавычек). Иначе, выведите «NO» (без кавычек).

ПримерыВходные данные

1 3
P.P

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

NO

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

2 2
PP
PP

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

YES

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

2 2
PP
P#

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

NO