CF1284G.Seollal

It is only a few days until Seollal (Korean Lunar New Year), and Jaehyun has invited his family to his garden. There are kids among the guests. To make the gathering more fun for the kids, Jaehyun is going to run a game of hide-and-seek.

The garden can be represented by a $n \times m$ grid of unit cells. Some (possibly zero) cells are blocked by rocks, and the remaining cells are free. Two cells are neighbors if they share an edge. Each cell has up to 4 neighbors: two in the horizontal direction and two in the vertical direction.

Since the garden is represented as a grid, we can classify the cells in the garden as either "black" or "white". The top-left cell is black, and two cells which are neighbors must be different colors. Cell indices are 1-based, so the top-left corner of the garden is cell $(1, 1)$.

Jaehyun wants to turn his garden into a maze by placing some walls between two cells. Walls can only be placed between neighboring cells. If the wall is placed between two neighboring cells $a$ and $b$, then the two cells $a$ and $b$ are not neighboring from that point. One can walk directly between two neighboring cells if and only if there is no wall directly between them.

A maze must have the following property. For each pair of free cells in the maze, there must be exactly one simple path between them. A simple path between cells $a$ and $b$ is a sequence of free cells in which the first cell is $a$, the last cell is $b$, all cells are distinct, and any two consecutive cells are neighbors which are not directly blocked by a wall.

At first, kids will gather in cell $(1, 1)$, and start the hide-and-seek game. A kid can hide in a cell if and only if that cell is free, it is not $(1, 1)$, and has exactly one free neighbor. Jaehyun planted roses in the black cells, so it's dangerous if the kids hide there. So Jaehyun wants to create a maze where the kids can only hide in white cells.

You are given the map of the garden as input. Your task is to help Jaehyun create a maze.

距离春节（韩国农历新年）仅有几天了，Jaehyun 邀请了他的家人来到自家花园。宾客中有一些孩子。为了让孩子玩得更开心，Jaehyun 打算组织一场捉迷藏游戏。

花园可表示为一个 $n \times m$ 的单位方格网格。其中部分（可能为零个）方格被岩石阻挡，其余方格为空闲方格。若两个方格共享一条边，则称它们为相邻方格。每个方格最多有 4 个相邻方格：水平方向两个，垂直方向两个。

由于花园以网格形式表示，我们可以将其中的方格划分为“黑色”或“白色”两类：左上角方格为黑色，且任意两个相邻方格颜色必须不同。方格坐标采用 1-基索引，因此花园左上角为方格 $(1, 1)$。

Jaehyun 计划通过在某些相邻方格之间放置墙壁，将花园改造成一座迷宫。墙壁只能放置在相邻方格之间；若在相邻方格 $a$ 和 $b$ 之间放置了一堵墙，则此后 $a$ 与 $b$ 不再视为相邻。当且仅当两个相邻方格之间没有墙壁直接阻隔时，人才能在这两个方格之间直接通行。

该迷宫须满足如下性质：对迷宫中任意一对空闲方格，其间恰好存在唯一一条简单路径。所谓方格 $a$ 与 $b$ 之间的简单路径，是指一个由空闲方格构成的序列，其首项为 $a$，末项为 $b$，所有方格互不相同，且序列中任意两个连续方格均为相邻方格，且二者之间无墙壁直接阻隔。

游戏开始时，孩子们将全部聚集在方格 $(1, 1)$，然后开始捉迷藏。一个孩子能躲藏在一个方格中，当且仅当该方格是空闲的、不是 $(1, 1)$，且恰好只有一个空闲相邻方格。Jaehyun 已在所有黑色方格中种植了玫瑰，若孩子躲在这些方格中会有危险。因此，Jaehyun 希望构造出一种迷宫布局，使得孩子只能躲在白色方格中。

你将获得花园的地图作为输入。你的任务是帮助 Jaehyun 构造这样一座迷宫。

Your program will be judged in multiple test cases.

The first line contains the number of test cases $t$. ($1 \le t \le 100$). Afterward, $t$ test cases with the described format will be given.

The first line of a test contains two integers $n, m$ ($2 \le n, m \le 20$), the size of the grid.

In the next $n$ line of a test contains a string of length $m$, consisting of the following characters (without any whitespace):

• O: A free cell.
• X: A rock.

It is guaranteed that the first cell (cell $(1, 1)$) is free, and every free cell is reachable from $(1, 1)$.

If $t \geq 2$ is satisfied, then the size of the grid will satisfy $n \le 10, m \le 10$. In other words, if any grid with size $n \gt 10$ or $m \gt 10$ is given as an input, then it will be the only input on the test case ($t = 1$).

你的程序将在多个测试用例中进行评测。

第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后将给出 $t$ 个符合所述格式的测试用例。

每个测试用例的第一行包含两个整数 $n, m$（$2 \le n, m \le 20$），表示网格的尺寸。

接下来的 $n$ 行中，每行包含一个长度为 $m$ 的字符串，该字符串仅由以下字符组成（不含任何空白字符）：

• O：一个空闲格子。
• X：一块岩石。

保证起始格子（即格子 $(1, 1)$）为空闲格子，且每个空闲格子均可从 $(1, 1)$ 到达。

若满足 $t \geq 2$，则网格尺寸将满足 $n \le 10, m \le 10$。换言之，若输入中存在任一网格满足 $n > 10$ 或 $m > 10$，则该测试用例必为唯一输入（即 $t = 1$）。

For each test case, print the following:

If there are no possible mazes, print a single line NO.

Otherwise, print a single line YES, followed by a grid of size $(2n-1) \times (2m-1)$ denoting the found maze. The rules for displaying the maze follows. All cells are indexed in 1-base.

• For all $1 \le i \le n, 1 \le j \le m$, if the cell $(i, j)$ is free cell, print 'O' in the cell $(2i-1, 2j-1)$. Otherwise, print 'X' in the cell $(2i-1, 2j-1)$.
• For all $1 \le i \le n, 1 \le j \le m-1$, if the neighboring cell $(i, j), (i, j+1)$ have wall blocking it, print ' ' in the cell $(2i-1, 2j)$. Otherwise, print any printable character except spaces in the cell $(2i-1, 2j)$. A printable character has an ASCII code in range $[32, 126]$: This includes spaces and alphanumeric characters.
• For all $1 \le i \le n-1, 1 \le j \le m$, if the neighboring cell $(i, j), (i+1, j)$ have wall blocking it, print ' ' in the cell $(2i, 2j-1)$. Otherwise, print any printable character except spaces in the cell $(2i, 2j-1)$
• For all $1 \le i \le n-1, 1 \le j \le m-1$, print any printable character in the cell $(2i, 2j)$.

Please, be careful about trailing newline characters or spaces. Each row of the grid should contain exactly $2m-1$ characters, and rows should be separated by a newline character. Trailing spaces must not be omitted in a row.

对于每个测试用例，输出如下内容：

• 如果不存在可能的迷宫，则输出一行 NO。

• 否则，先输出一行 YES，然后输出一个大小为 $(2n-1) \times (2m-1)$ 的网格，表示所构造出的迷宫。迷宫的显示规则如下（所有单元格均采用 1-索引）：

  • 对所有 $1 \le i \le n,\, 1 \le j \le m$：若单元格 $(i, j)$ 是空地，则在单元格 $(2i-1, 2j-1)$ 处输出 'O'；否则在单元格 $(2i-1, 2j-1)$ 处输出 'X'。

  • 对所有 $1 \le i \le n,\, 1 \le j \le m-1$：若相邻单元格 $(i, j)$ 与 $(i, j+1)$ 之间存在一堵墙阻隔，则在单元格 $(2i-1, 2j)$ 处输出空格 ' '；否则在单元格 $(2i-1, 2j)$ 处输出任意一个非空格的可打印字符。可打印字符指 ASCII 码在区间 $[32, 126]$ 内的字符（包含空格及字母数字字符等）。

  • 对所有 $1 \le i \le n-1,\, 1 \le j \le m$：若相邻单元格 $(i, j)$ 与 $(i+1, j)$ 之间存在一堵墙阻隔，则在单元格 $(2i, 2j-1)$ 处输出空格 ' '；否则在单元格 $(2i, 2j-1)$ 处输出任意一个非空格的可打印字符。

  • 对所有 $1 \le i \le n-1,\, 1 \le j \le m-1$：在单元格 $(2i, 2j)$ 处输出任意一个可打印字符。

请注意避免多余的末尾换行符或空格。网格的每一行必须恰好包含 $2m-1$ 个字符，各行之间以换行符分隔。每行末尾的空格不得省略。