数据结构基础

【题目描述】

深度优先搜索法（DFS）：想象一只老鼠，在一座不见天日的迷宫内，老鼠在入口处进去，要从出口出来。那老鼠会怎么走？当然是这样的：老鼠如果遇到直路，就一直往前走，如果遇到分叉路口，就任意选择其中的一个继续往下走，如果遇到死胡同，就退回到最近的一个分叉路口，选择另一条道路再走下去，如果遇到了出口，老鼠的旅途就算结束了。深度优先搜索法的基本原则就是这样：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同），则退回头另选通路继续搜索（用堆栈实现），直到找到条件的目标为止。

输入一个图，试DFS输出访问顺序

【输入格式】

第一行两个数n,m，表示n个结点数和m条边

随后m行，每行两个数x,y，表示x和y有边相连。

【输出格式】

输出n行，依次为DFS访问的结点顺序

【输入样例】

8 10

1 2

1 3

2 4

2 5

3 6

3 7

4 8

5 8

6 8

7 8

【输出样例】

1

3

7

8

6

5

2

4