← 返回题目列表

Codeforces · 1696/F

F. 树木恢复

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

钓鱼王子喜欢树。树是无环的连通无向图。

Fishingprince 有一个包含 $$$n$$$ 个顶点的树。顶点编号为 $$$1$$$ 到 $$$n$$$。令 $$$d(x,y)$$$ 表示树上从顶点 $$$x$$$ 到顶点 $$$y$$$ 的最短距离,假设每条边的长度为 $$$1$$$。

然而,这棵树在一次事故中丢失了。幸运的是,钓鱼王子还记得一些关于这棵树的信息。更具体地说,对于每个整数三元组 $$$x,y,z$$$ ($$$1\le x<y\le n$$$, $$$1\le z\le n$$$),他会记住是否 $$$d(x,z)=d(y,z)$$$ 。

帮助他恢复树的结构,或者报告不存在满足约束的树。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 200$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 100$$$) — 树中的顶点数。

然后是 $$$n-1$$$ 行。这些$$$n-1$$$行中的第$$$i$$$行包含$$$n-i$$$长度为$$$n$$$的字符串,由0和1组成。如果第$$$i$$$行的第$$$j$$$字符串中的第$$$k$$$字符为0,则意味着$$$d(i,k)\ne d(i+j,k)$$$;如果第$$$i$$$行的第$$$j$$$个字符串中的第$$$k$$$个字符为1,则表示$$$d(i,k)=d(i+j,k)$$$。

保证在一个输入文件中,

- 最多有 $$$2$$$ 测试用例,其中 $$$n>50$$$;
- 最多有 $$$5$$$ 测试用例,其中 $$$n>20$$$。

输出

对于每个测试用例:

- 如果不存在答案,则输出No;
- 否则,在第一行输出 Yes。然后输出$$$n-1$$$行。每行应包含两个整数 $$$x,y$$$ ($$$1\le x,y\le n$$$),表示树的顶点 $$$x$$$ 和 $$$y$$$ 之间的边。如果有多个解决方案,请打印其中一个。

打印“是”和“否”时,可以以任何大小写(大写或小写)打印每个字母。

示例

输入 #1

5
2
00
2
10
3
001 000
000
3
001 010
000
5
00000 01001 00000 01100
00000 10000 00000
00000 11010
00000

输出 #1

Yes
1 2
No
Yes
1 3
2 3
No
Yes
1 2
1 4
2 3
2 5