【基础】Codeforces本地调试模板

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include<bits/stdc++.h>
using namespace std;

/* abbr */
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

/* typedef for long long */

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;

/* typedef for other */

typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;

/* typedef for point */

//typedef pii point;
//#define x first
//#define y second

/* typedef for vector */

typedef vector<int> vi;
typedef vector<ll> vl;

/* constant number */

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const ld PI = acos(-1.0);
const int MOD = 998244353;

namespace Solver {

    const int MAXN = 100005;

    int n, m, k;
    int u[MAXN];
    int v[MAXN];

    bool vis[MAXN];
    unordered_set<int> G[MAXN];

    queue<int> Q;
    vector<int> clique;

    /* Methods */

    void InitOnce() {
#ifdef LOCAL
        freopen("A.txt", "r", stdin);
#endif // LOCAL
        int t;
        scanf("%d", &t);
        for(int i = 1; i < MAXN; ++i) {
            G[i].reserve(128);
            G[i].max_load_factor(0.85);
        }
    }

    void Read() {
        if(scanf("%d%d%d", &n, &m, &k) == -1)
            exit(0);
        for(int i = 1; i <= m; ++i)
            scanf("%d%d", &u[i], &v[i]);
#ifdef LOCAL
        static int tc = 0;
        printf("

===== Case #%d =====
", ++tc);
#endif // LOCAL
    }

    void Init() {
        for(int i = 1; i <= n; ++i)
            G[i].clear();
        memset(vis, 0, sizeof(vis[0]) * (n + 1));
        while(!Q.empty())
            Q.pop();
        clique.clear();
    }

    void Solve() {
        Read();
        if(k == 1) {
            puts("2");
            puts("1");
            return;
        }
        if(1LL * k * (k - 1) / 2 > m) {
            puts("-1");
            return;
        }
        Init();
        for(int i = 1; i <= m; ++i) {
            G[u[i]].insert(v[i]);
            G[v[i]].insert(u[i]);
        }
        for(int i = 1; i <= n; ++i) {
            if((int)G[i].size() <= k - 1) {
                vis[i] = 1;
                Q.push(i);
            }
        }
        while(!Q.empty()) {
            int u = Q.front();
            Q.pop();
            if((int)G[u].size() == k - 1 && clique.empty()) {
                clique.push_back(u);
                for(int v : G[u]) {
                    if((int)G[v].size() < k - 1) {
                        clique.clear();
                        break;
                    }
                    clique.push_back(v);
                }
                for(int u : clique) {
                    for(int v : clique) {
                        if(v == u)
                            continue;
                        if(!G[u].count(v)) {
                            clique.clear();
                            break;
                        }
                    }
                }
            }
            for(int v : G[u]) {
                G[v].erase(u);
                if(!vis[v] && ((int)G[v].size() <= k - 1)) {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
            G[u].clear();
        }
        int subset_siz = count(vis + 1, vis + 1 + n, 0);
        if(subset_siz != 0) {
            printf("1 %d
", subset_siz);
            for(int i = 1; i <= n; ++i) {
                if(vis[i] == 0)
                    printf("%d ", i);
            }
            puts("");
            return;
        }
        if(!clique.empty()) {
            puts("2");
            for(int u : clique)
                printf("%d ", u);
            puts("");
            return;
        }

        puts("-1");
        return;
    }

}

int main() {
    Solver::InitOnce();
    while(true)
        Solver::Solve();
    return 0;
}