题目描述

一张无向连通图中有 $n$ 个顶点，顶点编号为 $1,2,\ldots,n$，图中共有 $m$ 条无向边。

请从顶点 $s$ 出发进行深度优先遍历，并输出遍历序列。为了使答案唯一，每次从当前顶点继续搜索时，应优先访问编号较小的尚未访问的相邻顶点。

输入格式

第一行输入两个整数 $n,m$。

接下来 $m$ 行，每行输入两个整数 $u,v$，表示顶点 $u$ 与顶点 $v$ 之间有一条无向边。

最后一行输入一个整数 $s$，表示遍历的起点。

输出格式

输出一行 $n$ 个整数，表示从 $s$ 开始、按题目约定得到的深度优先遍历序列。相邻两个整数之间用一个空格分隔。

数据范围与约定

• $1\le n\le 1000$；
• $n-1\le m\le 5000$；
• 输入保证图为无向连通简单图。

可见测试数据

输入数据 1

4 5
1 2
1 3
1 4
2 4
3 4
1

输出数据 1

1 2 4 3

输入数据 2

1 0
1

输出数据 2

1

输入数据 3

5 4
1 3
3 2
3 5
5 4
3

输出数据 3

3 1 2 5 4