eolymp
bolt
Try our new interface for solving problems
Problems

Depth First Search

Depth First Search

Time limit 1 second
Memory limit 128 MiB

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