题目描述

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 in the spanning tree its degree is not larger than $\frac{n}{2}$.

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

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating 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$) indicating the number of vertices and edges in the graph.

For the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating that there is an edge connecting vertex $u_i$ and $v_i$. Please note that there might be self loops or multiple edges.

It's guaranteed that the given graph is connected. It's also guaranteed that the sum of $n$ of all test cases will not exceed $5 \times 10^5$, also the sum of $m$ of all test cases will not exceed $10^6$.

输出格式

For each test case, if such spanning tree exists first output Yes in one line, then for the following $(n-1)$ lines print two integers $p_i$ and $q_i$ on the $i$-th line separated by one space, indicating that there is an edge connecting vertex $p_i$ and $q_i$ in the spanning tree. If no valid spanning tree exists just output No in one line.

题目大意

题目描述

给定一张 $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$。

保证图连通。

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

提示

Note

For the first sample test case, the maximum degree among all vertices in the spanning tree is 3 (both vertex 1 and vertex 4 has a degree of 3). As $3 \le \frac{6}{2}$ this is a valid answer.

For the second sample test case, it's obvious that any spanning tree will have a vertex with degree of 2, as $2 > \frac{3}{2}$ no valid answer exists.