本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-10 19:14:10

思路：

可以先考虑将不经过一号点的连通分量找出来。

然后若连通分量个数 $>D$ 则无解（因为无法通过选 $D$ 条边而使其联通）。

否则对于 $1$ 连接每个连通分量的边任选一条，然后剩余的边随便选即可。

最后对于每个和 $1$ 相连的点，从他 dfs 一遍，当然不经过 $1$ 节点，对于每个点若当前位于它联通就将这条边加上并继续 dfs，否则跳过。

Code：

代码写的有点丑（

#include <bits\/stdc++.h>

using namespace std;

int n, m, D;
int idx, st[200010];
vector<int> e[200010];
int vis[200010], stt[200010];
map<pair<int, int>, int> ma1;

void dfs(int u) {
	st[u] = idx;
	for (auto v : e[u]) {
		if (v != 1 && !st[v]) {
			dfs(v);
		}
	}
}

void dfs1(int u) {
	vis[u] = 1;
	for (auto v : e[u]) {
		if (v != 1 && !vis[v]) {
			\/\/ cout << u << ' ' << v << "---\n";
			ma1[{u, v}] = 1;
			dfs1(v);
		}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &D);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		if (u > v) swap(u, v);
		e[u].push_back(v);
		e[v].push_back(u);
	}

	if (e[1].size() < D) {
		puts("NO");
		\/\/ cout << 1 << endl;
		return 0;
	}

	for (auto v : e[1])
		if (!st[v]) {
			++idx;
			dfs(v);	
		}

	for (auto v : e[1]) {
		if (stt[st[v]]) continue;
		stt[st[v]] = true;
		--D;
		if (D < 0) {
			puts("NO");
			return 0;
		}
		vis[v] = true;
		ma1[{1, v}] = 1;
	}

	for (auto v : e[1]) {
		if (D) {
			if (!vis[v]) {
				vis[v] = true;
				--D;
				ma1[{1, v}] = true;
			}
		}
	}

	puts("YES");

	for (auto v : e[1]){
		if (ma1.count({1, v})) {
			\/\/ cout << v << endl;
			dfs1(v);
		}
	}

	for (auto [u, v] : ma1) printf("%d %d\n", u.first, u.second);
	return 0;
}