题目描述

读入一个用邻接矩阵存储的无向连通图，输出它的深度优先遍历。

输入格式

第一行一个正整数n(1≤n≤10)，表示图中顶点数；

接下来输入n行n列的邻接矩阵a，a[i][j]=1代表顶点i和顶点j之间有边相连，a[i][j]=0代表顶点i和顶点j之间没有边相连。

输出格式

输出1~n的某一种排列，表示从顶点1开始，对该图进行深度优先遍历的顶点序列，相邻两个顶点之间用空格分隔。如果有多个遍历序列，输出字典序最小的。

输入/输出样例

8
0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 0 1 1
0 1 0 0 0 1 0 0
0 1 0 0 0 1 0 0
0 0 0 1 1 0 0 0
0 0 1 0 0 0 0 1
0 0 1 0 0 0 1 0

1 2 4 6 5 3 7 8

说明/提示

时间1000ms，内存256MiB