题目内容

给定一个无向图，顶点编号从 $1$ 到 $n$；从顶点 $1$ 出发，进行深度优先搜索(DFS)，当某个顶点有多个邻接点时，按照编号从小到大的顺序依次访问，输出遍历过程中访问顶点的顺序。

$1 \le n \le 100$，$0 \le m \le 100$。若不连通，DFS 从顶点 $1$ 出发无法遍历所有顶点，输出只包含可达顶点。输入保证没有自环如 $(i,i)$，即顶点到自身的边；同时输入保证不会有多条相同的边，如 $(1,2)$ 出现两次。

输入描述

• 整数 $n$, $m$：表示顶点数和边数；
• 二维数组 graph：每个元素有两个整数 $u$, $v$，表示 $u$ 和 $v$ 之间有一条无向边；

输出描述

• 数组：数组元素表示深度优先搜索访问顶点的顺序（从 $1$ 开始）；

样例1

输入

6,5,[[1,2],[1,3],[2,4],[3,5],[3,6]]

输出

[1,2,4,3,5,6]

说明

• 从 $1$ 出发，邻接点有 $\{2,3\}$，选小的 $2$
• 从 $2$ 出发，邻接点有 $\{1,4\}$，$1$ 已访问，选 $4$
• $4$ 没有未访问邻接点，回溯到 $2$，回溯到 $1$，下一个未访问的是 $3$
• 从 $3$ 出发，邻接点有 $\{1,5,6\}$，$1$ 已访问，选小的 $5$
• $5$ 没有未访问邻接点，回溯到 $3$，下一个未访问的是 $6$；$6$ 结束，遍历完成。最终访问顺序为 $[1,2,4,3,5,6]$。

样例2

输入

5,2,[[1,2],[3,4]]

输出

[1,2]

说明

• 从 $1$ 出发，邻接点有 $\{2\}$，选 $2$
• 从 $2$ 出发，邻接点有 $\{1\}$，$1$ 已访问，没有未访问邻接点，回溯到 $1$
• $1$ 没有其他未访问邻接点，遍历结束。顶点 $3$、$4$、$5$ 与 $1$ 不连通，无法到达，因此不输出。最终访问顺序为 $[1,2]$。