Depth-First Search

Problem Statement

Implement depth-first search in an undirected graph.

During the traversal, always select the smallest unvisited vertex as the next one.

Input

Your first line will contain $v$ and $e$ as space-separated integers. $v$ represents the number of vertices in the graph, labelled from $0$ to $v-1$, and $e$ represents the number of edges in the graph.

Your next line will contain $s$, the source vertex to start the DFS from.

Your next $e$ lines will contain $2$ space-separated numbers, specifying that there is an edge between the two specified vertices.

Output

The DFS traversal, separated by line breaks.

Constraints

For all test cases:

• $2 \le v \le 10^3$
• $0 \le s \le v-1$
• $1 \le e \le 10^6$

Example 1

7 6
0
0 1
0 2
1 3
1 4
2 5
2 6

0
1
3
4
2
5
6

Python Template

v, e = map(int, input().split())
s = input()
edges = [tuple(map(int, input().split(" "))) for _ in range(e)]

# print(...)

Recursive Limit

Python has this thing called a recursion limit which is pretty bad. If you want to bypass it, put the following magic words at the start of your file...

import sys
sys.setrecursionlimit(1000000)