这是问题的简单版本。版本之间的差异在于,在该版本中,对 $$$n$$$ 的约束较低。只有解决了该问题的所有版本,您才能破解。
你曾经有一棵带有 $$$n$$$ 个节点的无向树。为了使树看起来更有趣,您决定为每个 $$$n-1$$$ 边分配任意方向。
随着时间的推移,你忘记了树的结构。然而,你发现了一个记录了 之后 边的方向已被指定,对于所有满足$$$1\le u,v\le n$$$的有序对$$$(u,v)$$$,$$$u$$$是否可以到达$$$v$$$$$$^{\text{*}}$$$。
你想从注释给出的信息中找出树的结构和边的方向。确定是否存在可能的解决方案并构建一个。如果有多种解决方案,则只需找到其中一种即可。
$$$^{\text{*}}$$$对于有向图,我们说$$$x$$$可以到达$$$y$$$当且仅当存在节点序列$$$u_1,u_2,\ldots,u_k$$$使得$$$u_1=x,u_k=y$$$并且对于所有$$$i$$$ $$$2$$$到$$$k$$$,存在有向边$$$u_{i-1}\rightarrow u_i$$$。特别是,一个节点总是可以到达它自己。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 500$$$) 表示树的节点数。
以下 $$$n$$$ 行包含字符串 $$$s_i$$$。 $$$s_i$$$ 的长度为$$$n$$$,仅由$$$0$$$ 和$$$1$$$ 组成。当且仅当边定向后 $$$i$$$ 能够到达 $$$j$$$ 时,$$$s_i$$$ 的第 $$$j$$$ 个字符是 $$$1$$$。
保证所有测试用例的$$$n^3$$$总和不超过$$$500^3$$$。
输出
对于每个测试用例,如果存在解决方案,则输出 $$$\texttt{Yes}$$$,否则打印 $$$\texttt{No}$$$。如果答案是 $$$\texttt{Yes}$$$,则在下面的行中输出所构造边的描述。
输出 $$$n-1$$$ 线,表示有向边。每行应包含两个整数$$$x$$$和$$$y$$$,表示边有向后,存在有向边$$$x\rightarrow y$$$。如果有多个解决方案,请打印其中任何一个。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
示例
输入复制
11410001111101000014111101110010011140011011100110001410000110001011114100001101010111151000001011001110001000001510000110001010110111000015100000110100100011101000141100010000110001411100100001001013100111101
输出复制
Yes2 32 43 1NoNoYes2 34 14 2NoNoYes2 13 13 54 3NoNoYes1 21 34 2Yes2 33 1
注意
对于第一个测试用例,节点 $$$1$$$ 和 $$$4$$$ 只能到达自身,节点 $$$2$$$ 可以到达每个节点,节点 $$$3$$$ 只能到达节点 $$$1$$$ 和 $$$3$$$。构造的边满足这个约束。
对于第二个测试用例,可以证明不存在可能的解决方案。