408274: GYM103075 G Рудольф и лампочки

G. Рудольф и лампочкиограничение по времени на тест2 секундыограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

Рудольфу подарили шкатулку с необычным замком-головоломкой. Замок представляет собой квадратную сетку размера $$$N \times N$$$, в каждой клетке которой находится лампочка.

Горизонтальные ряды лампочек нумеруются числами от $$$1$$$ до $$$N$$$ сверху вниз, вертикальные — числами от $$$1$$$ до $$$N$$$ слева направо. Таким образом, например, лампочка в верхнем правом углу имеет координаты $$$(1; N)$$$, а лампочка в нижнем левом углу — $$$(N; 1)$$$.

Если Рудольф нажмёт на некоторую лампочку, то она поменяет своё состояние (то есть погаснет, если она горела, либо зажжётся, если не горела). Кроме того, при этом поменяют своё состояние все лампочки, соседние с нажатой по стороне.

Шкатулка откроется, если Рудольф сможет зажечь все лампочки. Помогите ему понять, на какие из них для этого нужно нажать.

Обратите внимание, что минимизировать количество ходов не требуется, но Рудольф должен сделать не более $$$1000$$$ ходов.

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

Первая строка содержит целое число $$$N$$$ ($$$1 \le N \le 30$$$) — размер головоломки.

Следующие $$$N$$$ строк описывают начальное состояние головоломки. Каждая из них содержит $$$N$$$ символов $$$A_{ij}$$$ ($$$A_{ij} \in \{\texttt{*}, \texttt{.}\}$$$). Символ $$$\texttt{*}$$$ обозначает включенную лампочку, символ $$$\texttt{.}$$$ — выключенную.

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

В первой строке выведите YES, если Рудольф сможет сделать так, чтобы все лампочки горели, либо NO, если не сможет.

Если решение существует, во второй строке выведите целое число $$$K$$$ — количество действий, которое требуется сделать Рудольфу. Число $$$K$$$ не должно превышать $$$1000$$$.

В следующих $$$K$$$ строках выведите по два целых числа — координаты лампочек, на которые нужно нажать.

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

3
...
...
...

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

YES
5
1 1
1 3
2 2
3 1
3 3

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

4
.*.*
*.*.
.*.*
*.*.

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

NO