Depth First Search

Get a tree

The connected undirected graph without loops and multiple edges is given. You are allowed to remove the edges from it. Obtain a tree from the graph.


The first line contains the number of vertices n (1n100) and the number of edges m of the graph. The next m pairs of numbers define the edges. It is guaranteed that the graph is connected.


Print n - 1 pairs of numbers - the edges that will be included in a tree. The edges can be displayed in any order.


Time limit 1 second
Memory limit 128 MiB
Input example #1
4 4
1 2
2 3
3 4
4 1
Output example #1
1 2
2 3
3 4