Background

YSGHYYDS

Problem Description

YSGH has an $n \times m$ Go board. Initially, each cell is either empty or contains a black stone. It is guaranteed that all black stones are connected.

In Go, the “liberties” of a stone are defined as the set of all empty cells adjacent to it.

Let the cell in row $i$ and column $j$ be $(i, j)$.

Two same-colored stones at $(i_1, j_1)$ and $(i_2, j_2)$ are considered adjacent if $|i_1 - i_2| + |j_1 - j_2| = 1$, meaning they are in the same connected component.

The “liberties” of a connected component are the union of the liberties of all stones in that component.

A white move is legal if and only if, after placing the stone, either the liberties of the connected component containing that white stone are at least $1$, or the liberties of the black connected component become $0$.

For example, in the figure below, the green cells are all liberties of the black connected component.

Definition of a “living group”: no matter how many consecutive moves the opponent makes, as long as every move is legal, the liberties of that connected component are always at least $1$.

Please determine whether this black connected component is a “living group”.

If it is, output YES; otherwise, output NO.

This problem has multiple test cases.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case:

The first line contains two positive integers $n, m$, meaning the board size is $n \times m$.

Then follow $n$ lines, each a string of length $m$. The $j$-th character of the $i$-th line indicates whether there is a stone at position $(i, j)$. . means empty, and * means a black stone.

Output Format

If the black group is “living”, output YES; otherwise, output NO.

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

NO
YES
NO

1
1 3
.*.

YES

Hint

[Sample Explanation #1]

Test case 1:

White plays $(1,1),(2,1),(3,2),(3,3),(3,4),(1,5),(2,5),(1,3)$ in order, which makes the liberties of the black connected component become $0$.

Let @ denote white stones. Then the final position is:

@*@*@
@***@
.@@@.

Test case 2:

For example, if White first plays $(1,1)$, then White will never be able to play at $(1,3)$ and $(2,1)$ afterward, causing the liberties of the black group to always be at least $1$. Therefore, the black group is “living”.

Test case 3:

A final position that makes the liberties of the black connected component equal to $0$:

@*@@.
@***@
**@**
*@.@*
**@**
*****

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the data: $1 \le n, m \le 2 \times {10}^3$, $1 \le T \le {10}^5$. Each cell of the initial board is either . or *, and there is at least one ., and at least one *. It is guaranteed that black stones are connected. The sum of $n \times m$ over each test point is at most $4 \times {10}^6$.

• Subtask 1 (9 points): $n = 1$.
• Subtask 2 (10 points): $n = 2$, $m = 3$.
• Subtask 3 (16 points): the number of . is at most $7$, $n, m \le 10$, $T \le 50$.
• Subtask 4 (24 points): the number of . is at most $14$, $n, m \le 10$, $T \le 50$.
• Subtask 5 (15 points): $n, m \ge 3$, and all boundary cells of the input position are .. That is, $\forall (i, j)$, if $i = 1 \lor i = n \lor j = 1 \lor j = m$, then $(i, j)$ must be empty.
• Subtask 6 (26 points): no special constraints.

P.S. Froggy and uyom are both (amateur 4-dan brothers who have not played for a long time), feel free to find us and beat us up.

Translated by ChatGPT 5