小班探险山洞

题目描述

小班来到一座山洞探险。山洞一共有 n 个洞穴，编号 1∼n，洞穴之间有 m 条双向通道。 小班可以选择任意一个洞穴作为探险起点，探险规则：不能重复进入同一个洞穴。 请使用深度优先搜索，按照DFS遍历顺序输出小班从起点能够到达的所有洞穴。

输入格式

第一行三个整数 n,m,s，分别代表洞穴数量、通道数量、探险起点编号。 接下来 m 行，每行两个整数 a,b，表示洞穴 a 和洞穴 b 之间有通道相连。

输出格式

一行若干个整数，为DFS遍历洞穴的顺序，数字之间用空格隔开。

样例输入

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

样例输出

2 1 5 6 7 3 4

提示

深度优先搜索：优先沿着一条通道往深处走，走到没有新洞穴可以探索时，原路折返，尝试其他还没走过的通道。