AT_agc069_b [AGC069B] Pair Guessing

[problemUrl]: https://atcoder.jp/contests/agc069/tasks/agc069_b $ N $ 個の、長さ $ N $ の $ 01 $ 文字列 $ S_1,\ldots,S_N $ が与えられます。$ S_i $ の $ j $ 文字目を $ S_{i,j} $ と表します。ここで、$ S_{i,j}=\ $`1` を満たす整数組 $ (i,j) $ が少なくとも一つ存在することが制約より保証されています。 高橋君と青木君が以下のようなゲームを行います。 1. 高橋君が $ 1\ \leq\ i,j\ \leq\ N,\ S_{i,j}=\ $`1` を満たす整数組 $ (i,j) $ を $ 1 $ つ選ぶ。 2. $ 0 $ 回以上 $ N $ 回以下、青木君が高橋君に質問を行う。各質問では青木君が $ 1\leq\ i',j'\ \leq\ N $ を満たす整数組 $ (i',j') $ を選び、「$ i=i' $ と $ j=j' $ のうち少なくとも一方が成り立つ」の真偽を高橋君から教えてもらう。 3. 青木君が $ (i,j) $ を予想する。予想が当たっていれば青木君の勝ち、そうでなければ負けとなる。 青木君は高橋君が選ぶ $ (i,j) $ の候補、すなわち $ S_1,\ldots,S_N $ を知った状態でゲームを行います。また、上記2では以前の質問に対する返事を聞いたうえで $ (i',\ j') $ を選ぶことができます。 青木君が適切な戦略を取った場合、高橋君の $ (i,j) $ の選び方や運によらず必ずゲームに勝てるかどうかを判定してください。 $ 1 $ つの入力につきテストケースは $ T $ 個あります。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ case_1 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ S_1 $ $ \vdots $ $ S_N $

各テストケースに対し、青木君が必ずゲームに勝てるならば `Yes` と、そうでなければ `No` と出力せよ。

### 制約 - $ 1\ \leq\ T\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ N\ \leq\ 500 $ - $ 1 $ つの入力の中のテストケースすべてにわたる $ N^2 $ の総和は $ 500^2 $ 以下である - $ S_i $ は長さ $ N $ の $ 01 $ 文字列 - $ S_{i,j}=\ $ `1` を満たす整数組 $ (i,j) $ が少なくとも一つ存在する ### Sample Explanation 1 $ 1 $ 番目のテストケースに対するゲームの一例を以下に示します。 1. 高橋君が $ S_{i,j}=\ $`1` を満たす $ (i,j) $ として $ (2,2) $ を選ぶ。 2. 青木君が $ 2 $ 回質問を行う。$ 1 $ 回目の質問では $ (i',j')=(1,1) $ として、高橋君から「$ i=1 $ と $ j=1 $ のうち少なくとも一方が成り立つ」が偽であると教えてもらう。$ 2 $ 回目の質問では $ (i',j')=(2,2) $ として、高橋君から「$ i=2 $ と $ j=2 $ の少なくとも一方が成り立つ」が真であると教えてもらう。 3. 青木君が $ (i,j)=(2,2) $ と予想する。この予想は当たっているため、青木君の勝ちである。 これはあくまでゲームの一例であり、青木君の戦略が適切とは限りません。しかし、青木君が適切な戦略を取った場合には必ず青木君がゲームに勝つため、$ 1 $ 番目のテストケースに対する出力は `Yes` になります。