Problems
Depth First Search
Depth First Search
The undirected graph is given. Start a depth-first search from the given vertex v and print the vertex numbers in the order of their first visit.
Input data
The first line contains the number of vertices n~(n \le 100) and edges m of the graph. Each of the following m lines contains two vertices a and b — an undirected edge of the graph. The last line contains the vertex v.
Output data
Start a depth-first search from vertex v and print the vertex numbers in the order of their first visit.
Examples
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