考虑一个由 $$$n$$$ 组成的数组 $$$a$$$ 不同 上面写着 整数。的 笛卡尔树 $$$a$$$ 的 被定义为 独特 二叉树$$$^{\text{*}}$$$满足以下条件:
- 树由 $$$n$$$ 个顶点组成,标记从 $$$1$$$ 到 $$$n$$$;
- 对于所有顶点对 $$$(i,j)$$$,使得 $$$i$$$ 是 $$$j$$$ 的父节点$$$^{\text{†}}$$$,$$$a_i \gt a_j$$$;
- 对于任意顶点$$$i$$$,$$$i$$$的左子树$$$^{\text{‡}}$$$中的所有顶点的标签都小于$$$i$$$;
- 对于任何顶点 $$$i$$$,$$$i$$$ 右子树中的所有顶点的标签都大于 $$$i$$$。
将 $$$r(a)$$$ 表示为笛卡尔树的根,并将 $$$f_a(i)$$$ 表示为笛卡尔树中 $$$i$$$ 的父代。
定义 $$$E_a=\{(i,f_a(i)) \mid 1 \le i \le n, i \ne r(a)\}$$$。
考虑长度为 $$$n$$$ 的排列$$$^{\text{§}}$$$ $$$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$$$ 始终存在。
$$$^{\text{*}}$$$二叉树是有根树,其中每个节点最多有$$$2$$$个子节点,称为左子节点和右子节点。
$$$^{\text{†}}$$$顶点$$$v$$$的父顶点是从$$$v$$$到根的简单路径上的第一个顶点。根没有父级。
$$$^{\text{‡}}$$$顶点 $$$v$$$ 的子树是 $$$v$$$ 的子图、其所有后代以及它们之间的所有边。
$$$^{\text{§}}$$$长度$$$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$$$ 行的第 $$$i$$$ 行包含长度为 $$$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$$$。
示例
输入复制
320110301110001040101001010010110
输出复制
1 22 1 33 1 2 4
注意