至曾是英雄的您

YSGHYYDS

YSGH 有一个 $n\times m$ 的围棋棋盘，初始时，每个位置要么是空的，要么有一个黑棋棋子。**保证黑棋是连通的。** 在围棋中，一个棋子的「气」是与它相邻的所有**空**位置构成的集合。 设棋盘上第 $i$ 行第 $j$ 个位置为 $(i,j)$。 两个分别在 $(i_1,j_1)$ 和 $(i_2,j_2)$ 的**同色**棋子如果满足 $|i_1-i_2|+|j_1-j_2|=1$，就认为是相邻的，也就是在同一个连通块里。 一个连通块的「气」是这个连通块中所有棋子的「气」的并集。 白方走一步棋是合法的，当且仅当走完这手棋之后这个棋子所在连通块的「气」大于等于 $1$ 或者黑棋连通块的「气」等于 $0$。 比如下图，绿色的位置都是黑棋连通块的「气」。  「活棋」的定义：无论对方连续走多少手棋，在每步棋都是合法的情况下，该连通块的「气」都大于等于 $1$。 请你判断这个黑棋连通块是否是「活棋」。 如果是，输出 `YES`，否则输出 `NO`。 **本题有多测。**

第一行，一个正整数 $T$，表示数据组数。 对于每组数据： 第一行，两个正整数 $n, m$，表示棋盘的大小为 $n \times m$。 接下来 $n$ 行，每行一个长度为 $m$ 的字符串。第 $i$ 行第 $j$ 个字符表示棋盘上位置为 $(i, j)$ 的地方是否有棋子。`.` 表示空格，`*` 表示黑棋子。

如果黑棋是「活棋」，输出 `YES`，否则输出 `NO`。

3
3 5
.*.*.
.***.
.....
2 5
.*.*.
.***.
6 5
.*...
.***.
**.**
*...*
**.**
*****

NO
YES
NO

1
1 3
.*.

YES

**【样例解释 #1】** 第 1 组数据： 白棋依次走 $(1,1),(2,1),(3,2),(3,3),(3,4),(1,5),(2,5),(1,3)$ 即可使得黑棋连通块的「气」变成 $0$ 了。 不妨用 `@` 表示白棋，那么最终局面就是： ```plain @*@*@ @***@ .@@@. ``` 第 2 组数据： 比方说白棋先走 $(1,1)$ 那么白棋之后就再也走不到 $(1,3)$ 和 $(2,1)$ 了，导致黑棋的「气」永远大于等于 $1$，所以黑棋是「活棋」。 第 3 组数据： 最终使得黑棋连通块的「气」等于 $0$ 的局面： ```plain @*@@. @***@ **@** *@.@* **@** ***** ``` --- **【数据范围】** **本题采用捆绑测试。** 对于 $100 \%$ 的数据，$1 \le n, m \le 2 \times {10}^3$，$1 \le T \le {10}^5$。输入的初始棋盘的每个位置要么是 `.`，要么是 `*`，并且至少有一个 `.`，至少有一个 `*`。**保证黑棋是连通的。** 保证每个测试点的 $n \times m$ 之和都小于等于 $4 \times {10}^6$。 - Subtask 1（9 points）：$n = 1$。 - Subtask 2（10 points）：$n = 2$，$m = 3$。 - Subtask 3（16 points）：保证 `.` 的个数不超过 $7$，$n, m \le 10$，$T \le 50$。 - Subtask 4（24 points）：保证 `.` 的个数不超过 $14$，$n, m \le 10$，$T \le 50$。 - Subtask 5（15 points）：$n, m \ge 3$，输入局面的边界上都是 `.`。即 $\forall (i, j)$，如果 $i = 1 \lor i = n \lor j = 1 \lor j = m$，则 $(i, j)$ 一定是空地。 - Subtask 6（26 points）：无特殊限制。 --- --- --- P.S. Froggy 和 uyom 都是（很久没下棋的）业余四段哥，欢迎找我们然后把我们虐一顿。