P Clique

#include<bits/stdc++.h>
#include"ypglpk.hpp"
using namespace std;
using namespace ypglpk;

//{
//#pragma gcc optimize("Ofast,unroll-loops")
//#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native")
//#define int long long
//#define double long double
#define MP make_pair
#define F first
#define S second
#define MOD 1000000007
//}

vector<bitset<80>> edge, mxclq;

void solve(bitset<80> R, bitset<80> P, bitset<80> X, int N)
{
    if (P.none() && X.none())
        mxclq.push_back(R);
    else
    {
        int u = -1;
        for (int i = 0; i < N; i++)
            if ((P[i] || X[i]) && (u == -1 || edge[i].count() > edge[u].count()))
                u = i;

        bitset<80> Pp = P & (~edge[u]);
        for (int i = 0; i < N; i++)
            if (Pp[i])
            {
                bitset<80> v;
                v[i] = true;

                solve(R | v, P & edge[i], X & edge[i], N);
                P = P & ~v;
                X = X | v;
            }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        int N, M;
        cin >> N >> M, edge.resize(N);
        for (int i = 0; i < N; i++)
            edge[i].reset();

        for (int i = 0; i < M; i++)
        {
            int u, v;
            cin >> u >> v;
            edge[u][v] = edge[v][u] = true;
        }

        bitset<80> R, P, X;
        for (int i = 0; i < N; i++)
            P[i] = true;
        mxclq.clear(), solve(R, P, X, N);

        int C = mxclq.size(), NC = N * C;
        vector<vector<double>> A;
        vector<double> B;

        // 0 <= x[i][j] <= 1, 0 <= z[i] <= 1
        for (int i = 0; i < NC + C; i++)
        {
            vector<double> tv(NC + C);
            tv[i] = -1, A.push_back(tv), B.push_back(0);
            tv[i] = 1, A.push_back(tv), B.push_back(1);
        }

        // x[i][j] <= 0 if i is not in clique j
        for (int i = 0; i < N; i++)
            for (int j = 0; j < C; j++)
                if (!mxclq[j][i])
                {
                    vector<double> tv(NC + C);
                    tv[i * C + j] = 1, A.push_back(tv), B.push_back(0);
                }

        // x[i][j] <= z[j]
        for (int i = 0; i < N; i++)
            for (int j = 0; j < C; j++)
            {
                vector<double> tv(NC + C);
                tv[i * C + j] = 1, tv[NC + j] = -1;
                A.push_back(tv), B.push_back(0);
            }

        // for 0 <= j < C, sum(x[i][j]) = 1
        for (int i = 0; i < N; i++)
        {
            vector<double> tv(NC + C);
            for (int j = 0; j < C; j++)
                tv[i * C + j] = 1;
            A.push_back(tv), B.push_back(1);
            for (int j = 0; j < C; j++)
                tv[i * C + j] = -1;
            A.push_back(tv), B.push_back(-1);
        }

        // minimize sum(z[i]) -> maximize -sum(z[i])
        vector<double> c(NC + C);
        for (int i = 0; i < C; i++)
            c[NC + i] = -1;

        pair<double, vector<double>> res = mixed_integer_linear_programming(A, B, c, vector<bool>(NC + C, true));
        cout << -res.F << '\n';
        for (int i = 0; i < C; i++)
            if (res.S[NC + i])
            {
                vector<int> v;
                for (int j = 0; j < N; j++)
                    if (res.S[j * C + i])
                        v.push_back(j);

                cout << v.size();
                for (int j : v)
                    cout << ' ' << j;
                cout << '\n';
            }
    }

    return 0;
}

//      *****  *****  *   *  *      *****  *   *  *****  *****
//        *   *   *  *   *  *        *    **  *    *    *   *
//       *   *   *  *****  *        *    * * *    *    *****
//   *  *   *   *    *    *        *    *  **    *    *
//  ****   *****    *    *****  *****  *   *    *    *

//     *   *   ***   *   *  **
//    *   *  *   *  *   *  **
//   * * *  *****  *****  **
//  * * *  *   *  *   *
//  * *   *   *  *   *  **