E. Castlefall
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alter's friends are playing a game of castlefall! The game has $$$N$$$ players, labelled $$$1$$$ through $$$N$$$, and $$$M$$$ words, labeled $$$1$$$ through $$$M$$$. Each player is assigned to exactly one of two non-empty teams of possibly different sizes, and each team is given one of the $$$M$$$ words. Note that the two teams are given different words.

Since players do not know which team they are on, each player has announced a clue. Specifically, the $$$i$$$-th player has a word in the set $$$S_i$$$.

Since Alter doesn't want to think, he asks you to help him answer the following question: Is it possible to uniquely determine the teams and the words corresponding to each team? If so, Alter will also ask you what the words are.

Input

The first line contains $$$T$$$ ($$$1\le T\le 20$$$), the number of independent test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$1\le N \le 20$$$, $$$1 \le M\le 10^5$$$).

In the following $$$N$$$ lines, the $$$i$$$-th line contains a binary string $$$s_i$$$ of length $$$M$$$. If the $$$j$$$-th character of $$$s_i$$$ is $$$1$$$, then the $$$i$$$-th player can possibly have the $$$j$$$-th word, that is, $$$j$$$ is in the set $$$S_i$$$. Otherwise, it is not possible for the $$$i$$$-th player to have the $$$j$$$-th word, or equivalently, $$$j$$$ is not in the set $$$S_i$$$.

It is guaranteed that the sum of $$$M$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

—

Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-2$$$ satisfy $$$N\le 10$$$, $$$M\le 10^3$$$.

Tests $$$3-8$$$ satisfy $$$N\le 10$$$.

Tests $$$9-20$$$ satisfy no additional constraints.

Output

For each test case, output a single line with "Yes" if it is possible to uniquely determine both the teams and the words corresponding to each team, or "No" otherwise. If the output is Yes, output a second line with two integers, corresponding to the words given to the two teams, in increasing order.

Example
Input
3
3 4
0010
0110
0110
3 4
0010
0001
0110
3 4
0001
1100
1001
Output
No
Yes
3 4
No
Note

In the first sample test case, here are some possible teams:

  1. The first two players are on a team with word 3, and the third player is on a team with word 2.
  2. The first player is on a team with word 3 and the second and third players are on a team with word 2.

Since there is not a unique team, the answer is No.

In the second test case, the unique team combination is: The first and third players are on a team with word 3, and the second player is on a team with word 4.

—

Problem Idea: jay_jayjay

Problem Preparation: jay_jayjay

Occurrences: Novice J / Advanced E