CF1749E.Cactus Wall

Monocarp is playing Minecraft and wants to build a wall of cacti. He wants to build it on a field of sand of the size of $n \times m$ cells. Initially, there are cacti in some cells of the field. Note that, in Minecraft, cacti cannot grow on cells adjacent to each other by side — and the initial field meets this restriction. Monocarp can plant new cacti (they must also fulfil the aforementioned condition). He can't chop down any of the cacti that are already growing on the field — he doesn't have an axe, and the cacti are too prickly for his hands.

Monocarp believes that the wall is complete if there is no path from the top row of the field to the bottom row, such that:

• each two consecutive cells in the path are adjacent by side;
• no cell belonging to the path contains a cactus.

Your task is to plant the minimum number of cacti to build a wall (or to report that this is impossible).

Monocarp 正在玩《我的世界》（Minecraft），他想建造一堵仙人掌墙。他打算在一块 $n \times m$ 的沙土地上建造这堵墙。初始时，沙土地的某些格子中已长有仙人掌。注意，在《我的世界》中，仙人掌不能生长在彼此正交相邻（即上下左右相邻）的格子中——而初始场地满足这一限制条件。Monocarp 可以在空地上种植新的仙人掌（新种的仙人掌也必须满足上述限制条件）。但他无法砍掉任何已存在的仙人掌——因为他没有斧头，而且仙人掌太扎手了。

Monocarp 认为，当不存在从场地最顶行到最底行的路径时，这堵墙才算建成。该路径需满足：

• 路径中任意两个连续格子必须正交相邻（即上下左右相邻）；
• 路径中经过的每个格子都不能含有仙人掌。

你的任务是：种植最少数量的新仙人掌，使得墙建成；若不可能建成，则报告该情况。

The first line contains a single integer $t$ ($1 \le t \le 10^3$) — number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n, m \le 2 \cdot 10^5$; $n \times m \le 4 \cdot 10^5$) — the number of rows and columns, respectively.

Then $n$ rows follow, $i$-th row contains a string $s_i$ of length $m$, where $s_{i, j}$ is '#', if a cactus grows at the intersection of the $i$-th row and the $j$-th column. Otherwise, $s_{i, j}$ is '.'.

The sum of $n \times m$ over all test cases does not exceed $4 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 2 \cdot 10^5$；且 $n \times m \le 4 \cdot 10^5$），分别表示行数和列数。

接下来是 $n$ 行，其中第 $i$ 行包含一个长度为 $m$ 的字符串 $s_i$；若在第 $i$ 行与第 $j$ 列的交点处生长着一株仙人掌，则 $s_{i, j}$ 为 '#'；否则为 '.'。

所有测试用例中 $n \times m$ 的总和不超过 $4 \cdot 10^5$。

For each test case, print NO in the first line if it is impossible to build a cactus wall without breaking the rules. Otherwise, print YES in the first line, then print $n$ lines of $m$ characters each — the field itself, where the $j$-th character of the $i$-th line is equal to '#', if there is a cactus on the intersection of the $i$-th row and the $j$-th column, otherwise it is '.'. If there are multiple optimal answers, print any of them.

对于每个测试用例，如果无法在不违反规则的情况下建造仙人掌墙，则在第一行输出 NO。否则，在第一行输出 YES，然后输出 $n$ 行，每行包含 $m$ 个字符——即该场地本身；其中第 $i$ 行的第 $j$ 个字符为 #，表示在第 $i$ 行与第 $j$ 列的交点处有一株仙人掌；否则为 .。若存在多个最优解，输出任意一个即可。