n个点，m条边，没有边权，然后每次问你找出一颗生成树，使得其中的点的度数最大
只要随便找一个度数最大的点，然后与他相连的边用并查集瞎合并就可以，然后就是遍历一下其他遍，也合并一下即可
或者从度数最大的点开始bfs，形成一个“菊花图”（别问我，别人告诉我的，我从来不知道有这个东西）
代码:
#include <bits/stdc++.h>
#include <time.h>using namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) {return a < -eps ? -1 : a > eps;
}
inline int cmp(db a,db b) {return sign(a - b);
}
ll mul(ll a,ll b,ll c) {ll res = 1;while(b) {if(b & 1) res *= a,res %= c;a *= a,a %= c,b >>= 1;}return res;
}
ll phi(ll x) {ll res = x;for(ll i = 2; i * i <= x; i++) {if(x % i == 0) res = res / i * (i - 1);while(x % i == 0) x /= i;}if(x > 1) res = res / x * (x - 1);return res;
}
int fa[maxn];
int Find(int x) {if(x != fa[x]) return fa[x] = Find(fa[x]);return fa[x];
}
ll c,n,k;
int a[maxn];
int b[maxn];
P p[maxn];
void unionn(int x,int y) {int X=Find(x);int fb=Find(y);if(X!=fb) fa[X]=fb;
}//将被边连接的两个独立集合合并
int m;
int vis[maxn];
int main() {ios::sync_with_stdio(false);while(cin >> n >> m) {memset(vis,0,sizeof(vis));for(int i = 1; i <= m; i++) {cin >> p[i].first >> p[i].second;vis[p[i].first]++;vis[p[i].second]++;}int Max = 0,id = 0;for(int i = 1;i <= n;i++){if(Max < vis[i]){Max = vis[i];id = i;}}vector<P>ans;int cnt = 0;for(int i=1; i<=n; i++) {fa[i]=i;}for(int i = 1;i <= m;i++){if(Find(p[i].first) != Find(p[i].second) && (id == p[i].first || id == p[i].second))unionn(p[i].first,p[i].second),cnt++,ans.push_back(p[i]),vis[i] = 1;}for(int i=1; i<=m; i++) {if(cnt==n-1) break;//当已经有n-1条边的时候，结束if(Find(p[i].first) != Find(p[i].second)) {unionn(p[i].first,p[i].second);cnt++;ans.push_back(p[i]);}}
// cout << ans.size() << endl;for(auto d:ans) {cout << d.first << " " << d.second << endl;}}cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}