分数: 1000 点
问题陈述
你被给予 N 字符串 S_1, \ldots, S_N,每个长度 N,仅包含 0 和 1。让 S_{i,j} 表示 j- 第一个字符 S_i。由约束条件保证至少存在一个整数对 (i, j) 满意 S_{i,j} = 1.
Takahashi 和 Aoki 玩以下游戏:
- Takahashi 选择一对整数 (i, j) 满意 1 \leq i, j \leq N 和 S_{i,j} =
1. - 青木至少问高桥 0 最多 N 问题。在每个问题中,Aoki 选择一个整数对 (i', j') 满意 1 \leq i', j' \leq N,高桥告诉青木是否“至少有一个 i = i' or j = j' 成立”是真还是假。
- 青木猜测 (i, j)。如果他猜对了,青木就赢了;如果他猜对了,青木就赢了。否则,他就输了。
青木知道可能的选择 (i, j) 高桥可以选择,那就是他知道 S_1, \ldots, S_N 玩游戏之前。另外,在第 2 步中,Aoki 可以选择 (i', j') 基于之前问题的答案。
判断青木是否总能赢得比赛,无论高桥的选择如何 (i, j) 和随机性,如果他使用适当的策略。
有 T 每个输入中的测试用例。
约束
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 500
- 总和 N^2 每个输入中的所有测试用例最多 500^2.
- S_i 是一个长度为的字符串 N 组成
0和1. - 至少有一个整数对 (i, j) 满意 S_{i,j} =
1.
输入
输入由标准输入按以下格式给出:
T case_1 \vdots case_T
每个测试用例均按以下格式给出:
N S_1 \vdots S_N
输出
对于每个测试用例,打印 Yes 如果青木总能赢得比赛,并且 No 否则。
示例输入 1
3 2 01 11 2 11 11 10 0101011110 1100100001 1101100000 0111101010 1000011001 1110101010 1110110100 1110000110 0000001011 1001111100
示例输出 1
Yes No Yes
第一个测试用例中,游戏示例如下:
- 高桥选择 (i, j) = (2, 2) 满意 S_{i,j}=\
1. - 青木问两个问题。在第一个问题中,他选择 (i', j') = (1, 1)。高桥告诉他“至少有一个 i = 1 or j = 1 成立”是错误的。在第二个问题中,他选择 (i', j') = (2, 2)。高桥告诉他“至少有一个 i = 2 or j = 2 成立”为真。
- 青木猜测 (i, j) = (2, 2)。由于他的猜测是正确的,青木获胜。
这只是游戏的一个例子,青木的策略可能不是最优的。然而,如果 Aoki 使用适当的策略,他总能赢得比赛,所以第一个测试用例的输出是 Yes.