e-olymp
Competitions

Depth First Search

Depth First Search

Undirected graph is given. Run depth first search from the given vertex v and print the numbers of vertices in the order of their first visit.

Input

First line contains number of vertices n (n100) and edges m of undirected graph. Each of the next m lines contains two vertices a and b - an undirected edge of the graph. The last line contains vertex v.

Output

Run dfs(v) and print in one line the numbers of vertices in the order of their first visit.

prb8760.gif

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 3
1 2
2 3
1 3
2
Output example #1
2 1 3 
Input example #2
5 3
1 3
2 3
2 5
5
Output example #2
5 2 3 1