← 返回题目列表

Codeforces · 1054/G

G. 新路网

中文机器翻译题面 查看原题

某个国家的国王$$$N$$$决定彻底重建道路网络。有 $$$n$$$ 人居住在该国,他们的数量从 $$$1$$$ 到 $$$n$$$。可以在任何公民 $$$a$$$ 的房屋和任何其他公民 $$$b$$$ 的房屋之间修建一条道路。任何一对公民之间不应有超过一条道路。道路网络必须连通,即应该能够从使用道路的任何人开始到达每个公民。为了节省资金,决定修建$$$n-1$$$道路,因此道路网络应该是一棵树。

然而,这并不像听起来那么容易,这就是国王向你求助的原因。这个国家有 $$$m$$$ 个秘密社区,每个社区都团结着一个非空的公民子集。国王不想与任何社区发生冲突,因此他希望构建网络,使每个社区成员的房屋在网络中形成一个相连的子树。当且仅当当我们从集合中删除所有其他顶点和除了连接顶点的边之外的所有边时,图仍然保持连接时,一组顶点形成连通子树。

帮助国王确定是否可以建造所需的道路网络,如果可以,就建造它。

输入

每个测试由一个或多个测试用例组成。

第一行包含一个整数 $$$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$$$ 社区的成员。保证字符串 $$$s_i$$$ 对于每个 $$$1 \leq i \leq m$$$ 至少包含一个字符“1”。

保证所有测试用例的$$$n$$$总和不超过$$$2000$$$,所有测试用例的$$$m$$$总和不超过$$$2000$$$。

输出

按照输入中给出的顺序打印所有测试用例的答案,每个测试用例都采用以下格式。

如果无法构建所需的道路网络,则打印“NO”(不带引号)。

否则在第一行打印“YES”(不带引号)。

在接下来的 $$$n-1$$$ 行中打印道路网络的描述:每行应包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq n$$$, $$$a \neq b$$$),表示您在公民 $$$a$$$ 和 $$$b$$$ 的房屋之间修建一条道路。

道路应形成一棵连通树,每个社区应形成一棵连通子树。

示例

输入 #1

2
4 3
0011
1110
0111
3 3
011
101
110

输出 #1

YES
1 3
2 3
3 4
NO

注意

在第一个示例中,您可以构建以下网络:

很容易看出,对于每个社区,其成员的所有房屋形成一个连接的子树。例如,$$$2$$$-nd 社区将公民 $$$1$$$、$$$2$$$、$$$3$$$ 联合起来。它们形成一个连通的子树,因为如果我们删除除了房屋 $$$1$$$、$$$2$$$、$$$3$$$ 以及它们之间的道路之外的所有内容,则会保留两条道路:$$$1$$$ 和 $$$3$$$ 之间以及 $$$2$$$ 和 $$$3$$$ 之间,形成连通图。

第二个例子中没有适合王的网络。