钓鱼王子喜欢树。树是无环的连通无向图。
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