图的深搜

题目描述

给定一个有 $N$ 个点和 $M$ 条边的无向图，从指定的起点 $S$ 开始进行深度优先搜索，并按访问顺序输出访问到的节点编号。

输入描述

第一行包含三个整数 $N$、$M$ 和 $S$，分别表示图的点数、边数和起点。 接下来 $M$ 行，每行两个整数 $u$ 和 $v$，表示节点 $u$ 和 $v$ 之间有一条边。

输出描述

按深度优先搜索的访问顺序输出节点编号，每个编号之间用空格隔开。

输入样例

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

输出样例

1 2 4 3 5

数据范围

• $1 \le N \le 1000$
• $1 \le M \le 10000$
• $1 \le S \le N$