#YDRS005A. 我爱云斗小课堂

我爱云斗小课堂

题目描述

云斗小课堂开课啦!小朋友们全部都坐在座位上。

现在有 nn 排座位,每排有 mm 个。正常条件下,所有小朋友都会尽量坐前排的座位,并且在同一排的座位中也会尽量坐在左边。

现在给你一个二维 01 矩阵表示每个座位的占用情况(1 表示有人,0 表示没人),请判断正常条件下有没有可能出现这个座位情况。

云斗小课堂实际上会在不同的场所开课 TT 次,所以你需要在每次开课时都对座位占用情况进行判断。

输入格式

输入的第一行有一个正整数 TT,表示开课次数。

对于云斗每一节课,都会先给出两个正整数 n,mn,m 表示这次开课时的座位行数和列数,再有 nn 行,每行一个长 mm 的 01 串,表示座位的占用情况。

输出格式

输出 TT 行,每行一个,分别表示第 1,2,,T1,2,\ldots,T 节课的座位占用情况是否可能在正常条件下出现,如果可能出现则输出 Yes,否则输出 No

样例 #1

样例输入 #1

5
3 5
11111
11100
00000
1 4
1011
2 3
110
110
1 1
0
1 1
1

样例输出 #1

Yes
No
No
Yes
Yes

提示

【样例解释】

云斗课堂一共开课了 55 次。

第一次开课来了 88 个小朋友,都按照正常条件就坐了。

第二次开课来了 33 个小朋友,按照正常条件,坐在第 11 行第 3,43,4 列的小朋友应该往左坐一些。

第三次开课来了 44 个小朋友,按照正常条件,第一排应该坐满,第二排的小朋友应该在最左边。

后两次开课提醒你,座位可以全部不坐人,也可以全部坐满。

【数据规模和约定】

本题共 1010 个测试点,每个测试点 1010 分。

测试点编号 nn\le mm\le 特殊性质
1,21,2 11 99
3,43,4 99 11
5,65,6 99 小朋友个数是mm 的倍数
7,87,8
9,109,10 3030

对于编号为奇数的测试点,保证 T=1T=1

对于全体数据,保证 1T1001\le T\le 1001n,m301\le n,m\le 30