Description

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

Input Format

多组数据，第一行，一个整数 $t$ 代表数据组数。

对于每组数据：

• 第一行两个整数 $n$, $m$，代表边数和点数；
• 接下来 $m$ 行，输入 $u_i,v_i$ 代表一条边（可能有重边和自环）。

Output Format

对于每组数据：

第一行输出 Yes 或 No 代表是否可行。

若可行，接下来 $n - 1$ 行输出每条生成树的边，顺序随意。

2
6 9
1 2
1 3
1 4
2 3
2 4
3 4
4 5
4 6
4 6
3 4
1 3
2 3
3 3
1 2

Yes
1 2
1 3
1 4
4 5
4 6
No

Hint

$2 \leq n \leq 10^5$，$n - 1\leq m \leq 2\times10^5$，$\sum n\leq5\times10^5$，$\sum m\leq10^6$。

保证图连通。