题目描述

已知图 $G$ 已用邻接矩阵存储，要求实现一下功能

• 编写一个程序，将图 $G$ 转化为邻接表
• 输出图的深度优先遍历结果（从节点 $1$ 开始遍历，序号从小到大）
• 输出图的广度优先遍历结果（从节点 $1$ 开始遍历，序号从小到大）

输入格式

第一行：节点总数 $n$

下面 $n$ 行：图 $G$ 的邻接矩阵

输出格式

第一行：图的深度优先遍历

第二行：图的广度优先遍历

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

1 2 6 4 5 3 7 8
1 2 3 4 6 5 7 8

数据范围

$1 \le n \le 1000$