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** (**n** ≤ **100**) 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.

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