#P18604. Graph Problem With Small n

Graph Problem With Small n

Graph Problem With Small n

给出一个有 nn 个顶点的简单无向图。对每对不同的顶点 (i,j)(i,j),判断是否存在一条从 ii 出发、在 jj 结束,并且恰好经过所有顶点一次的路径。

这样的路径称为哈密顿路径,具有 n−1n-1 条边。图不保证连通。

输入格式

第一行一个整数 nn,2≤n≤242\le n\le24。

随后 nn 行,每行一个长度为 nn 的二进制串。第 ii 行的第 jj 位为 1 表示顶点 i,ji,j 之间有边,否则为 0。矩阵对称,对角线全部为 0。

输出格式

输出 nn 行长度为 nn 的二进制串。第 ii 行第 jj 位在存在上述路径时为 1,否则为 0。所有对角线位置必须输出 0。

样例输入 1

4
0110
1010
1101
0010

样例输出 1

0001
0001
0000
1100

样例输入 2

6
010001
101000
010100
001010
000101
100010

样例输出 2

010001
101000
010100
001010
000101
100010

样例输入 3

4
0111
1011
1101
1110

样例输出 3

0111
1011
1101
1110

样例说明

第一组可行的无序端点对是 (1,4)(1,4)、(2,4)(2,4)。第二组是六个顶点的环,仅原图中相邻的顶点可以作为哈密顿路径的两端。第三组为完全图,所有不同顶点对都可行。