这是问题的困难版本。版本之间的区别在于,在这个版本中,对$$$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 8000$$$) 表示树的节点数。
以下 $$$n$$$ 行包含字符串 $$$s_i$$$。 $$$s_i$$$ 的长度为$$$n$$$,仅由$$$0$$$ 和$$$1$$$ 组成。当且仅当边定向后 $$$i$$$ 能够到达 $$$j$$$ 时,$$$s_i$$$ 的第 $$$j$$$ 个字符是 $$$1$$$。
保证所有测试用例的$$$n^2$$$总和不超过$$$8000^2$$$。
输出
对于每个测试用例,如果存在解决方案,则输出 $$$\texttt{Yes}$$$,否则打印 $$$\texttt{No}$$$。如果答案是 $$$\texttt{Yes}$$$,则在下面的行中输出所构造边的描述。
输出 $$$n-1$$$ 线,表示有向边。每行应包含两个整数$$$x$$$和$$$y$$$,表示边有向后,存在有向边$$$x\rightarrow y$$$。如果有多个解决方案,请打印其中任何一个。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。
示例
输入复制
11 4 1000 1111 1010 0001 4 1111 0111 0010 0111 4 0011 0111 0011 0001 4 1000 0110 0010 1111 4 1000 0110 1010 1111 5 10000 01011 00111 00010 00001 5 10000 11000 10101 10111 00001 5 10000 01101 00100 01110 10001 4 1100 0100 0011 0001 4 1110 0100 0010 0101 3 100 111 101
输出复制
Yes 2 3 2 4 3 1 No No Yes 2 3 4 1 4 2 No No Yes 2 1 3 1 3 5 4 3 No No Yes 1 2 1 3 4 2 Yes 2 3 3 1
注意
对于第一个测试用例,节点 $$$1$$$ 和 $$$4$$$ 只能到达自身,节点 $$$2$$$ 可以到达每个节点,节点 $$$3$$$ 只能到达节点 $$$1$$$ 和 $$$3$$$。构造的边满足这个约束。
对于第二个测试用例,可以证明不存在可能的解决方案。