CF2187G Many Cartesian Trees

给定一个由 $n$ 个互不相同整数组成的数组 $a$。数组 $a$ 的笛卡尔树被定义为一棵满足以下条件的唯一二叉树： - 该树包含 $n$ 个顶点，标号从 $1$ 到 $n$。 - 对于所有满足 $i$ 是 $j$ 的父节点的顶点对 $(i,j)$，都有 $a_i > a_j$。 - 对于任意顶点 $i$，其左子树中的所有顶点标号都小于 $i$。 - 对于任意顶点 $i$，其右子树中的所有顶点标号都大于 $i$。 记 $r(a)$ 为数组 $a$ 对应的笛卡尔树的根节点，$f_a(i)$ 表示在笛卡尔树中 $i$ 的父节点。 定义 $E_a=\{(i,f_a(i)) \mid 1 \le i \le n,\, i \ne r(a)\}$。 现有一个长度为 $n$ 的排列 $q$。定义一系列数组 $p_1,p_2,\ldots,p_n$，如下： - $p_1=q$； - 对于 $2 \le i \le n$，$p_i$ 由 $p_{i-1}$ 中的最小元素加上 $n$ 得到。可以证明所有 $p_i$ 的元素都互不相同。 现在给定 $n$ 和 $S=\bigcup\limits_{i=1}^n E_{p_i}$。为简化输入，$S$ 以 $n\times n$ 的二进制矩阵 $s$ 给出。$s_{i,j}$ 表示第 $i$ 行第 $j$ 列的字符。$s_{i,j}=1$ 当且仅当 $(i,j)\in S$。 请你找出任意一个排列 $q$，使得能通过上述过程得到集合 $S$。保证数据生成时一定存在合法的 $q$。 *注释： 1. 二叉树是有根树，每个节点最多有 $2$ 个子节点，分别称为左子节点和右子节点。 2. 顶点 $v$ 的父节点是从 $v$ 到根的简单路径上的第一个顶点。根节点没有父节点。 3. 顶点 $v$ 的子树指包含 $v$、$v$ 的所有后代及它们之间边的子图。 4. 长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个不同整数按任意顺序构成的数组。例如 $[2,3,1,5,4]$ 是排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$，但数组中有 $4$）。*

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。 每个测试用例的第一行包含整数 $n$（$2 \le n \le 3000$）——你需要寻找的排列 $q$ 的长度。 接下来 $n$ 行，每行是一个长度为 $n$ 的二进制字符串，表示 $s$ 的第 $i$ 行。保证所有 $1 \le i \le n$，都有 $s_{i,i}=0$。 保证测试数据生成时一定存在合法的 $q$。 并且所有测试用例的 $n^2$ 之和不超过 $9 \cdot 10^6$。

对每组测试用例，输出一行 $n$ 个整数 $q_1,q_2,\ldots,q_n$，表示你找到的排列 $q$。

 由 ChatGPT 5 翻译