第一个问题直接输出 $1 \sim n$ ,然后稍微求一个近似连通块,就可以获得 $80pts$ 的好成绩.

code:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int read(){
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)){
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}
const int N = 1e4 + 5, M = 2e5 + 5;
int T, n, m;
int tot, to[M], nxt[M], head[N];
int du[N], num, ans[N];
priority_queue <pair <int, int > > q;
bool flag[N];
void add(int u, int v){
    to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}
void init(){
    n = read(), m = read();
    while (q.size()) q.pop();
    memset(du, 0, sizeof(int) * (n + 1));
    memset(head, 0, sizeof(int) * (n + 1));
    memset(flag, 0, sizeof(int) * (n + 1));
    tot = num = 0;
    for (int i = 1; i <= m; i++){
        int u = read(), v = read();
        add(u, v); add(v, u);
        du[u]++, du[v]++;
    }
}
void solve(){
    for (int i = 1; i <= n; i++) q.push(make_pair(-du[i], i));
    while (q.size()){
        int x = q.top().second; q.pop();
        if (flag[x]) continue;
        ans[++num] = x;
        flag[x] = 1;
        for (int i = head[x]; i; i = nxt[i]){
            int y = to[i];
            flag[y] = 1;
        }
    }
}
void print(){
    printf("%d ", n);
    for (int i = 1; i <= n; i++) printf("%d ", i);
    printf("\n");
    printf("%d ", num);
    for (int i = 1; i <= num; i++) printf("%d ", ans[i]);
    printf("\n");
}
int main(){
    T = read();
    while (T--){
        init();
        solve();
        print();
    }
    return 0;
}