CF2208D2 Tree Orientation (Hard Version)

这是该问题的难度较高版本。两个版本的区别在于本版本中 $n$ 的约束更大。只有在你完成了此问题的所有版本后，才能进行 hack。 你曾经拥有一棵包含 $n$ 个节点的无向树。为了让这棵树变得更加有趣，你打算随意给每条 $n-1$ 条边赋予一个方向。 时光流逝，你已经忘记了你的树的结构。但你发现了一张记录，在所有边被赋予方向后，对于每一组有序对 $(u,v)$ 满足 $1\le u,v\le n$，都标记了 $u$ 是否能够到达 $v$。 你想根据这份信息，推断出可能的树的结构以及边的方向。如果有可能，请构造出任意一种解；如果有多个解，只需给出其中一种即可。 对于有向图，如果存在一组节点序列 $u_1,u_2,\ldots,u_k$，使得 $u_1=x,u_k=y$，并且对所有 $i$ 从 $2$ 到 $k$，有有向边 $u_{i-1}\rightarrow u_i$ 存在，则称 $x$ 可以到达 $y$。特别地，一个节点总可以到达它自己。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。 每个测试用例第一行包含一个整数 $n$（$2\le n\le 8000$），表示你的树有 $n$ 个节点。 接下来的 $n$ 行，每行包含一个长度为 $n$ 的字符串 $s_i$，仅包含字符 $0$ 和 $1$。如果第 $j$ 个字符为 $1$，表示 $i$ 能在边定向后到达 $j$。 保证所有测试用例的 $n^2$ 之和不超过 $8000^2$。

对于每个测试用例，如果存在解，输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。如果答案是 $\texttt{Yes}$，则在下一行输出你构造的边。 共输出 $n-1$ 行，每行两个正整数 $x$ 和 $y$，表示有一条定向后的有向边 $x\rightarrow y$。如果有多种方案，输出任意一种即可。 你可以用任意大小写输出答案（比如 "yEs", "yes", "Yes", "YES" 都可以被识别为肯定回答）。

对于第一个样例，节点 $1$ 和 $4$ 只能到达自身，节点 $2$ 可以到达所有节点，节点 $3$ 只能到达 $1$ 和 $3$。所构造的边满足这些约束。 对于第二个样例，可以证明不存在可行解。 由 ChatGPT 5 翻译