BFS Traversal

Easyjavapythonccppjavascript

Given an undirected graph and a starting vertex S, visit all reachable vertices using Breadth-First Search. When a vertex is expanded, consider its neighbours in increasing order.

Input Format

The first line contains two integers V and E. Each of the next E lines contains an undirected edge u v. The last line contains the starting vertex S.

Output Format

Print the BFS visit order (only reachable vertices), separated by single spaces.

Example 1

Input

Output

0 1 2 3 4

Explanation: BFS visits vertices level by level.

Input (stdin)

Output

Run your code to see output here...