Codeforces Round 1086 (Div. 2)——CF-2208-D2. Tree Orientation (Hard Version)

题目大意

题目描述
有一棵包含 $n$ 个节点的无向树，为了让它更有趣，你对它的 $n-1$ 条边任意指定了方向，将其变成了一棵有向树。
现在你忘记了这棵树的结构和边的方向，但你找到了一份记录，上面写着给边指定方向后，所有节点对之间的可达性。具体来说，给定 $n$ 个长度为 $n$ 的 01 字符串。如果第 $i$ 个字符串的第 $j$ 个字符为 1，则表示在有向树中，节点 $i$ 可以到达节点 $j$（必然存在一条从 $i$ 到 $j$ 的有向路径）；如果为 0 则表示无法到达。特别地，一个节点总是可以到达它自己。

你的任务是根据这个可达性信息，判断是否存在合法的树结构与边的方向。如果存在，请构造并输出任意一个满足条件的解；如果不存在，请输出 No。本题为 Hard 版本，与 Easy 版本的唯一区别是 $n$ 的数据范围更大。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 8000$），表示节点的数量。
接下来 $n$ 行，每行包含一个长度为 $n$ 的 01 字符串，表示可达性矩阵。
保证所有测试用例中 $n^2$ 的总和不超过 $8000^2$。

输出格式
对于每个测试用例，如果存在解，输出 Yes，并在接下来的 $n-1$ 行中输出构造的有向边。每行包含两个整数 $x$ 和 $y$，表示存在一条从 $x$ 指向 $y$ 的有向边。如果有多个解，输出任意一个即可。
如果不存在解，输出 No。
（输出 Yes 和 No 时不区分大小写，例如 yEs、YES 都会被接受）。

样例输入

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$。输出构造的边为 $2 \to 3$、$2 \to 4$、$3 \to 1$，这三条边构成了一棵合法的有向树，并且恰好满足上述可达性限制。
对于第二个测试用例，可以证明不存在任何合法的一棵树能够满足给定的可达性要求，因此输出 No。

思路讲解

Codeforces Round 1086 (Div. 2)——CF-2208-D1. Tree Orientation (Easy Version)

这道题目的简单版本确实是比较 easy 的。

然后，现在呢，就是

Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-E1. N-MEX (Constructive Version)

我觉得和这道题目还是

AC代码

源代码

心路历程（WA，TLE，MLE……）