T4 仙人掌方块 (cactus, 2s/256M)

玩过《Minecraft》吗？这是一款沙盒游戏，玩家可以在游戏内发挥自己的创造力和想象力，用游戏所给的方块来搭建属于自己的建筑。今天的主角就是：仙人掌方块。

为了简化，我们将游戏地图看成是一张 $N$ 行 $M$ 列的平面网格图。这个网格图上有些格子为空地，而有些格子已经放上了仙人掌。

仙人掌方块具有以下特性：

• 任意两个仙人掌方块都没有边相邻（即每个仙人掌方块的上下左右四个相邻格子都没有仙人掌）。保证初始地图的仙人掌符合这个特性。

你的任务是：在初始地图上，再种下最少数量的仙人掌，使得不存在一条从第一行到最后一行的只经过空地路径（路径不能斜着走，只能上下左右依次走一格），并输出一种方案。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每一组数据，第一行两个正整数 $N, M$。接下来输入一个 $N\times M$ 的字符矩阵，其中 . 表示空地，# 表示仙人掌。

输出格式

对于每一组数据，如果不能构造一种方案，输出一行 NO。

否则，先输出一行 YES，然后再输出一个 $N\times M$ 的字符矩阵，表示你构造的方案。注意要求新建造的仙人掌方块数量要最少。

样例输入

4
2 4
.#..
..#.
3 3
#.#
...
.#.
5 5
.....
.....
.....
.....
.....
4 3
#..
.#.
#.#
...

输出格式

YES
.#.#
#.#.
NO
YES
....#
...#.
..#..
.#...
#....
YES
#..
.#.
#.#
...

数据范围

• 对于 30% 的数据，$2 \le N, M \le 10, 1 \le T \le 5$；
• 对于 80% 的数据，$N\cdot M \le 5\times 10^4, \sum N\cdot M \le 5\times 10^4$；
• 对于 100% 的数据，$2 \le N, M \le 2\cdot 10^5, N\cdot M \le 2\cdot 10^6, \sum N\cdot M \le 2\times 10^6, 1\le T \le 100$.