CF1054G.New Road Network

The king of some country $N$ decided to completely rebuild the road network. There are $n$ people living in the country, they are enumerated from $1$ to $n$. It is possible to construct a road between the house of any citizen $a$ to the house of any other citizen $b$. There should not be more than one road between any pair of citizens. The road network must be connected, i.e. it should be possible to reach every citizen starting from anyone using roads. To save funds, it was decided to build exactly $n-1$ road, so the road network should be a tree.

However, it is not that easy as it sounds, that's why the king addressed you for help. There are $m$ secret communities in the country, each of them unites a non-empty subset of citizens. The king does not want to conflict with any of the communities, so he wants to build the network such that the houses of members of each society form a connected subtree in network. A set of vertices forms a connected subtree if and only if the graph remains connected when we delete all the other vertices and all edges but ones that connect the vertices from the set.

Help the king to determine if it is possible to build the desired road network, and if it is, build it.

某国国王 $N$ 决定彻底重建该国的道路网络。全国共有 $n$ 位居民，编号从 $1$ 到 $n$。可以在任意居民 $a$ 的住所与任意其他居民 $b$ 的住所之间修建一条道路；任意两位居民之间至多只能修建一条道路。道路网络必须是连通的，即：从任意一位居民出发，均可仅通过道路到达其余所有居民。为节省资金，决定恰好修建 $n-1$ 条道路，因此该道路网络应构成一棵树。

然而，问题并不像听起来那么简单，因此国王向你寻求帮助。全国共有 $m$ 个秘密社团，每个社团都联合了居民的一个非空子集。国王不希望与任何社团发生冲突，因此他要求所建道路网络满足：每个社团成员的住所构成网络中的一棵连通子树。一组顶点构成一棵连通子树，当且仅当：在原图中删去所有不属于该集合的顶点，以及所有至少有一个端点不属于该集合的边后，剩余图仍保持连通。

请帮助国王判断是否存在满足上述要求的道路网络；若存在，请构造出这样的一棵树。

Each test consists of one or more test cases.

The first line contains a single integer $t$ ($1 \leq t \leq 2000$) — the number of test cases.

The following lines describe the test cases, each in the following format.

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 2000$) — the number of citizens and the number of secret communities.

The next $m$ lines contain the description of the communities. The $i$-th of these lines contains a string $s_i$ of length $n$, consisting of characters '0' and '1'. The citizen with number $j$ is a member of the $i$-th community if and only if $s_{{i}{j}}=1$. It is guaranteed that the string $s_i$ contains at least one character '1' for each $1 \leq i \leq m$.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2000$ and the sum of $m$ for all test cases does not exceed $2000$.

每个测试包含一个或多个测试用例。

第一行包含一个整数 $t$（$1 \leq t \leq 2000$），表示测试用例的数量。

接下来的若干行描述各个测试用例，每个测试用例的格式如下：

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2000$），分别表示市民人数和秘密社团数量。

接下来 $m$ 行描述这些社团。其中第 $i$ 行包含一个长度为 $n$ 的字符串 $s_i$，由字符 '0' 和 '1' 组成。当且仅当 $s_{{i}{j}} = 1$ 时，编号为 $j$ 的市民属于第 $i$ 个社团。保证对每个 $1 \leq i \leq m$，字符串 $s_i$ 中至少包含一个字符 '1'。

保证所有测试用例的 $n$ 之和不超过 $2000$，且所有测试用例的 $m$ 之和不超过 $2000$。

Print the answer for all test cases in the order they are given in the input, each in the following format.

If there is no way to build the desired road network, print "NO" (without quotes).

Otherwise in the first line print "YES" (without quotes).

In the next $n-1$ lines print the description of the road network: each line should contain two integers $a$ and $b$ ($1 \leq a, b \leq n$, $a \neq b$) that denote you build a road between houses of citizens $a$ and $b$.

The roads should form a connected tree, and each community should form a connected subtree.

按输入中测试用例的顺序输出所有测试用例的答案，每个测试用例的输出格式如下：

• 如果无法构建满足要求的道路网络，则输出 "NO"（不带引号）。

• 否则，第一行输出 "YES"（不带引号）；
  接下来的 $n-1$ 行描述所构建的道路网络：每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq n$，且 $a \neq b$），表示在公民 $a$ 和公民 $b$ 的住宅之间修建一条道路。

所修建的道路必须构成一棵连通树，且每个社区必须构成一棵连通子树。

In the first example you can build the following network:

It is easy to see that for each community all the houses of its members form a connected subtree. For example, the $2$-nd community unites the citizens $1$, $2$, $3$. They form a connected subtree, because if we delete everything except the houses $1$, $2$, $3$ and the roads between them, two roads will remain: between $1$ and $3$ and between $2$ and $3$, forming a connected graph.

There is no network in the second example suitable for the king.

在第一个例子中，你可以构建如下网络：

容易看出，对每个社区而言，其所有成员的住宅构成一棵连通子树。例如，第 $2$ 个社区联合了市民 $1$、$2$、$3$。它们构成一棵连通子树，因为若仅保留住宅 $1$、$2$、$3$ 及其之间的道路，将剩下两条道路：$1$ 与 $3$ 之间、以及 $2$ 与 $3$ 之间，从而形成一张连通图。

第二个例子中不存在满足国王要求的网络。