P9625 [ICPC 2020 Nanjing R] Degree of Spanning Tree

给定一张 $n$ 个点 $m$ 条边的无向图，求一个生成树满足每个点的度数都不大于 $\frac{n}{2}$。

多组数据，第一行，一个整数 $t$ 代表数据组数。 对于每组数据： - 第一行两个整数 $n$, $m$，代表边数和点数； - 接下来 $m$ 行，输入 $u_i,v_i$ 代表一条边（可能有重边和自环）。

对于每组数据： 第一行输出 `Yes` 或 `No` 代表是否可行。 若可行，接下来 $n - 1$ 行输出每条生成树的边，顺序随意。

$2 \leq n \leq 10^5$，$n - 1\leq m \leq 2\times10^5$，$\sum n\leq5\times10^5$，$\sum m\leq10^6$。 保证图连通。