Spanning Tree with Degree Constraint

Given an undirected connected graph with n vertices and m edges, your task is to find a spanning tree of the graph such that for every vertex v in the spanning tree, its degree \( \deg(v) \) does not exceed \( \frac{n}{2} \). Recall that the degree of a vertex is the number of edges incident to it.

You are guaranteed that the input graph has at least one spanning tree satisfying the above condition.

inputFormat

The first line contains two integers n and m (2 ≤ n, m ≤ 10⁵), representing the number of vertices and edges respectively.

Each of the following m lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v), representing an undirected edge between vertices u and v.

It is guaranteed that the graph is connected and that there exists a spanning tree of the graph where for every vertex v, \( \deg(v) \leq \frac{n}{2} \).

outputFormat

Output exactly n - 1 lines. Each line should contain two integers u and v denoting an edge in the spanning tree. The spanning tree you output must be a subgraph of the given graph and satisfy that for every vertex v, its degree in the tree is at most \( \frac{n}{2} \).

sample

4 4
1 2
2 3
3 4
4 1

1 2
2 3
3 4