给您一个无向图,其顶点为 $$$n$$$,标记为从 $$$1$$$ 到 $$$n$$$。该图编码了大小为$$$n$$$的隐藏排列$$$^{\text{*}}$$$ $$$p$$$。 该图的构造如下:
- 对于每对整数 $$$1 \le i < j \le n$$$,当且仅当 $$$p_i < p_j$$$ 时,在顶点 $$$p_i$$$ 和顶点 $$$p_j$$$ 之间添加无向边。请注意,边不是添加在顶点 $$$i$$$ 和 $$$j$$$ 之间,而是添加在它们各自元素的顶点之间。请参阅注释部分以获得更好的理解。
你的任务是重建并输出排列$$$p$$$。可以证明排列$$$p$$$可以唯一确定。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$)。
接下来的 $$$n$$$ 行的第 $$$i$$$ 包含 $$$n$$$ 个字符的字符串 $$$g_{i, 1}g_{i, 2}\ldots g_{i, n}$$$ ($$$g_{i, j} = \mathtt{0}$$$ 或 $$$g_{i, j} = \mathtt{1}$$$) — 邻接矩阵。 $$$g_{i, j} = \mathtt{1}$$$ 当且仅当顶点 $$$i$$$ 和顶点 $$$j$$$ 之间存在边。
保证存在生成给定图的排列 $$$p$$$。还保证该图是无向的并且没有自环,这意味着 $$$g_{i, j} = g_{j, i}$$$ 和 $$$g_{i, i} = \mathtt{0}$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,输出 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ 表示重构的排列。
示例
输入 #1
3 1 0 5 00101 00101 11001 00001 11110 6 000000 000000 000000 000000 000000 000000
输出 #1
1 4 2 1 3 5 6 5 4 3 2 1
注意
在第一种情况下 $$$p = [1]$$$。由于不存在 $$$1 \le i < j \le n$$$ 对,因此图中没有边。
第二种情况的图表如下所示。例如,当我们选择 $$$i = 3$$$ 和 $$$j = 4$$$ 时,我们在顶点 $$$p_i = 1$$$ 和 $$$p_j = 3$$$ 之间添加一条边,因为 $$$p_i < p_j$$$。然而,当我们选择 $$$i = 2$$$ 和 $$$j = 3$$$ 时,$$$p_i = 2$$$ 和 $$$p_j = 1$$$,所以 $$$p_i < p_j$$$ 不成立。因此,我们不会在 $$$2$$$ 和 $$$1$$$ 之间添加边。
在第三种情况下,图中没有边,因此不存在使得 $$$p_i < p_j$$$ 的整数对 $$$1 \le i < j \le n$$$。因此,$$$p = [6, 5, 4, 3, 2, 1]$$$。