# Get a tree

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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.

## Examples

Input #1

Answer #1

Submissions 10K

Acceptance rate 54%