B. Find the Permutation

题意

有一个 $n$ 个顶点的无向图，顶点编号 $1$ 到 $n$。 该图编码了一个隐藏的排列 $p$（长度为 $n$，元素是 $1$ 到 $n$ 的整数）。

图的构造方式如下： 对于每一对整数 $1 \le i < j \le n$，检查 $p_i$ 和 $p_j$ 的值：

如果 $p_i < p_j$，则在 顶点 $p_i$ 和顶点 $p_j$ 之间添加一条无向边。 注意：边的端点不是 $i$ 和 $j$，而是它们的值 $p_i$ 和 $p_j$。

给定图（邻接矩阵），保证存在唯一的排列 $p$ 生成该图。 请还原并输出 $p$。

输入格式

第一行 $t$（$1 \le t \le 500$）

对于每个测试用例：

第一行 $n$（$1 \le n \le 1000$）

接下来 $n$ 行，每行一个长度为 $n$ 的字符串 $g_{i,1} \dots g_{i,n}$，$g_{i,j} \in {0,1}$ 表示邻接矩阵：$g_{i,j}=1$ 表示顶点 $i$ 与 $j$ 有边。

保证图无自环（$g_{i,i}=0$），无向（$g_{i,j}=g_{j,i}$）。

所有测试用例的 $n$ 之和 $\le 1000$。

输出格式

每个测试用例输出一行 $n$ 个整数 $p_1, p_2, \dots, p_n$。

3
1
0
5
00101
00101
11001
00001
11110
6
000000
000000
000000
000000
000000
000000

1 
4 2 1 3 5 
6 5 4 3 2 1 

注意：

在第一个样例中，p=[1]。因为不存在满足 1≤i<j≤n 的数对，所以图中没有边。 第二个样例对应的图如下所示。例如，当我们取 i=3、j=4 时，会在顶点 pi​=1 和 pj​=3 之间连一条边，因为 pi​<pj​。而当我们取 i=2、j=3 时，pi​=2、pj​=1，不满足 pi​<pj​，因此不在 2 和 1 之间连边。

在第三个样例中，图中没有边，这意味着不存在满足 1≤i<j≤n 且 pi​<pj​ 的整数对。因此，p=[6,5,4,3,2,1]。