给定一个包含 $n$ 个顶点和 $m$ 条边的无向连通图，你的任务是找到该图的一棵生成树，使得生成树中每个顶点的度数都不超过 $\frac{n}{2}$。

回想一下，顶点的度数是指与该顶点相连的边的数量。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 10^5, n - 1 \le m \le 2 \times 10^5$)，分别表示图的顶点数和边数。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示存在一条连接顶点 $u_i$ 和 $v_i$ 的边。请注意，图中可能存在自环或重边。

保证给定的图是连通的。同时保证所有测试数据的 $n$ 之和不超过 $5 \times 10^5$，所有测试数据的 $m$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，如果存在这样的生成树，首先输出一行 “Yes”（不含引号），然后在接下来的 $(n - 1)$ 行中，每行输出两个整数 $p_i$ 和 $q_i$，表示生成树中连接顶点 $p_i$ 和 $q_i$ 的一条边。如果不存在满足条件的生成树，则仅输出一行 “No”（不含引号）。

样例

样例输入 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

样例输出 1

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

说明

对于第一个样例测试数据，生成树中所有顶点的最大度数为 3（顶点 1 和顶点 4 的度数均为 3）。由于 $3 \le \frac{6}{2}$，这是一个合法的答案。

对于第二个样例测试数据，显然任何生成树都会有一个度数为 2 的顶点，由于 $2 > \frac{3}{2}$，因此不存在合法的答案。