Competitions

# 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.

#### Input

The first line contains the number of vertices **n** (**1** ≤ **n** ≤ **100**) 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.

#### Output

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

Input example #1

4 4 1 2 2 3 3 4 4 1

Output example #1

1 2 2 3 3 4