思路是第三篇题解

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

#define int long long

const int N=1e3+5;

int n,m;
vector<int> G[N],T[N];
bool vis[N],islef[N];
vector<int> vec,ans;
bool flg;

int deg[N];

void dfs(int u,int pa)
{
    vis[u]=1;
    int lef=0;
    for(int v:G[u])
        if(!vis[v]){
            dfs(v,u);deg[u]++,deg[v]++;
            T[u].emplace_back(v);
            T[v].emplace_back(u);
        }
}

void out(int u,int pa,int ed)
{
    if(flg) return;
    ans.push_back(u);
    if(u==ed){
        flg=1;
        return;
    }
    for(int v:T[u])
        if(v!=pa){
            out(v,u,ed);
            if(flg) return;
            ans.pop_back();
        }
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1,0);
    for(int i=2;i<=n;i++) if(deg[i]==1) vec.push_back(i),islef[i]=1;
    if((int)vec.size()>=n/3){
        cout<<"2\n";
        for(int i=0;i<n/3;i++)
            cout<<vec[i]<<' ';
        exit(0);
    }
    if(deg[1]==1) vec.push_back(1),islef[1]=1;
    sort(vec.begin(),vec.end());
    vec.insert(vec.begin(),0);
    cout<<"1\n";
    int sz=vec.size()-1;
    int res=(n+5)/6;
    for(int i=1;i<=(sz+1)/2;i++){
        res--;
        ans.clear();
        out(vec[i],0,vec[sz/2+i]);
        cout<<(int)ans.size()<<' ';
        for(int j:ans) cout<<j<<' ';
        cout<<'\n';
    }
    for(int i=1;i<=n&&res;i++){
        if(!islef[i]){
            cout<<"1 "<<i<<'\n';res--;
        }
    }
    return 0;
}