Degree of Spanning Tree

You are given an undirected connected graph with $n$ vertices and $m$ edges. Find a spanning tree of the graph such that every vertex in the tree has degree at most $\frac{n}{2}$.

The degree of a vertex is the number of edges connected to it.

The first line contains an integer $T$, the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^5$, $n-1 \le m \le 2 \times 10^5$), the number of vertices and edges.

The next $m$ lines each contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$), meaning there is an edge between vertices $u_i$ and $v_i$. The graph may contain self loops and multiple edges.

The graph is guaranteed to be connected. The sum of $n$ over all test cases does not exceed $5 \times 10^5$, and the sum of $m$ does not exceed $10^6$.

For each test case, if a valid spanning tree exists, print "Yes" on one line. Then print $n-1$ lines, each with two integers $p_i$ and $q_i$, meaning the tree contains an edge between $p_i$ and $q_i$.

If no valid spanning tree exists, print "No" on one line.

In the first sample, the maximum degree in the spanning tree is 3 (vertices 1 and 4 both have degree 3). Since $3 \le \frac{6}{2}$, the answer is valid.

In the second sample, every spanning tree has a vertex with degree 2. Since $2 > \frac{3}{2}$, no valid answer exists.