← 返回题目列表

Codeforces · 2208/D2

D2. 树方向(硬版)

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

这是问题的困难版本。版本之间的区别在于,在这个版本中,对$$$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$$$。构造的边满足这个约束。

对于第二个测试用例,可以证明不存在可能的解决方案。