题目描述

给定一个 $n \times m$ 的矩阵 $a$，其中每个元素的值均为 $0$ 或 $1$。

如果两个单元格在矩阵中上下相邻或左右相邻，则称它们是相邻的。仅在对角线方向相邻的两个单元格不视为相邻。

对于两个值为 $1$ 的单元格，如果可以从其中一个出发，每次移动到一个相邻且值为 $1$ 的单元格，最终到达另一个，则称这两个单元格是连通的。

请判断矩阵中是否至少存在一个值为 $1$ 的单元格，且所有值为 $1$ 的单元格均属于同一个连通块。

特别地，如果矩阵中不存在值为 $1$ 的单元格，则视为不连通。

输入格式

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

对于每个测试用例：

第一行包含两个正整数 $n$ 和 $m$（$1 \le n,m \le 10^{5}$），分别表示矩阵的行数和列数。

接下来 $n$ 行，每行包含一个长度恰好为 $m$ 的字符串，字符串仅由字符 0 和 1 组成。其中，第 $i$ 行字符串的第 $j$ 个字符表示矩阵元素 $a_{i,j}$。同一行的字符之间没有空格。

保证所有测试用例中 $n \times m$ 的总和不超过 $10^{7}$。

输出格式

对于每个测试用例，输出一行。

如果矩阵中至少存在一个值为 $1$ 的单元格，且所有值为 $1$ 的单元格均属于同一个连通块，则输出 Yes；否则输出 No。

7
1 1
0
1 1
1
2 2
10
01
3 3
110
010
011
1 5
01110
1 5
11011
5 5
11111
10001
10101
10001
11111

No
Yes
No
Yes
Yes
No
No

样例解释

• 连通路径只能经过值为 $1$ 的单元格，每次只能向上、下、左、右四个方向之一移动，且不能移出矩阵。

• 如果矩阵中恰好只有一个值为 $1$ 的单元格，则答案为 Yes。

• 如果矩阵中所有元素均为 $0$，则答案为 No。