You cannot submit for this problem because the homework's deadline is due.

Description

Implement Breadth First Search algorithm, represent the input graphs using the data structures developed in lab 5.

Format

Submit a tar or zip file including a script named bfs.ml or bfs.py.

Input

The graph is undirected, unweighted graph.
First line is the number of edges.
Following lines are each edge u v.

Output

One line consists of the result. The starting point should always be 0.

Sample IO

Input

4
0 2
0 7
3 7
4 7

Output

0 2 7 3 4 

One edge that is input first, is expected to search first (edge 3 7 and 4 7 in this example).