33006번 - Remodeling the Dungeon 2 스페셜 저지다국어

문제

The Queen of the Kingdom of Icpca resides in a castle peacefully. One day, she decided to remodel the dungeon of the castle.

The dungeon is a rectangular grid consisting of square cells. Some cells are enterable rooms, while others are duct spaces which are not enterable. All pairs of adjacent cells are separated by a wall. Some of the walls between two adjacent rooms are installed with a door to go back and forth. Any pair of rooms in the dungeon has connecting paths through these doors.

The Queen wants to remodel the dungeon so that there is only one unique path between any pair of rooms. Additionally, any pair of rooms both with only one door should be connected with a path going through an even number of doors. Due to the cost limitation, what can be done in the remodeling is only to block some (possibly zero) doors.

Your mission is to find a way to remodel the dungeon as the Queen wants.

입력

The input consists of a single test case in the following format.

$h$ $w$

$c_{1,1}c_{1,2} \cdots c_{1,2w+1}$

$c_{2,1}c_{2,2} \cdots c_{2,2w+1}$

$\vdots$

$c_{2h+1,1}c_{2h+1,2} \cdots c_{2h+1,2w+1}$

Two integers $h$ and $w$ mean that the dungeon size is $h \times w$. They are between 1ドル$ and 400ドル,ドル inclusive.

Each of the characters $c_{i,j}$ (1ドル ≤ i ≤ 2h + 1,ドル 1ドル ≤ j ≤ 2w + 1$) is either ‘.’ or ‘#’. These characters represent the configuration of the dungeon as follows.

• When both $i$ and $j$ are even, $c_{i,j}$ represents the cell located at the $i/2$-th row from the north and the $j/2$-th column from the west of the dungeon, referred to as cell $(i/2, j/2)$. Being ‘.’ indicates that the cell is a room, while ‘#’ indicates a duct space.
• When $i$ is odd and $j$ is even, it represents a wall. When $i = 1$ or $i = 2h+ 1,ドル it is a part of the outer wall of the dungeon. In this case, $c_{i,j}$ is always ‘#’. Otherwise, $c_{i,j}$ represents the wall between cells $((i - 1)/2, j/2)$ and $((i + 1)/2, j/2)$. Being ‘.’ indicates that the wall has a door, while ‘#’ indicates that it does not. Doors are installed only in walls between two rooms.
• When $i$ is even and $j$ is odd, it also represents a wall. When $j = 1$ or $j = 2w + 1,ドル it is a part of the outer wall of the dungeon. In this case, $c_{i,j}$ is always ‘#’. Otherwise, $c_{i,j}$ represents the wall between cells $(i/2,(j - 1)/2)$ and $(i/2,(j + 1)/2)$. Being ‘.’ indicates that the wall has a door, while ‘#’ indicates that it does not. Doors are installed only in walls between two rooms.
• When both $i$ and $j$ are odd, $c_{i,j}$ is always ‘#’, corresponding to an intersection of walls.

It is guaranteed that there is at least one room in the dungeon and any pair of rooms in the dungeon has one or more connecting paths.

출력

If it is impossible to remodel the dungeon as the Queen wants, output No. Otherwise, output Yes on the first line, followed by the configuration of the dungeon after the remodeling in the same format as the input. If there are multiple possible configurations, any one of them is acceptable.

제한

힌트