月赛的时候写了个随机，有没有人能 Hack 啊 /kk

大概思路：

• 先求独立集，方法是每次选度数最小的点尝试加入独立集，能加就加，达到了要求就输出
• 否则每次随机选一个起点 dfs，每次随机顺序访问边（如果有出点没被任何路径访问过就以 $0.9$ 的概率优先访问），直到走不下去了为止，访问过了所有点就输出

代码（没对输出的链去重，也懒得加了，只要什么都不输出就是卡掉了）

#include<bits/stdc++.h>
#include<sys/mman.h>
using namespace std;
struct _io {
    char* s;
    _io() : s((char*)mmap(0, 1 << 25, PROT_READ, MAP_PRIVATE, fileno(stdin), 0)) {}
    operator int() {
        int x = 0;
        while((*s) < '0'|| (*s) > '9')++s;
        while ((*s) >= '0'&& (*s) <= '9') x = x * 10 + ((*s++) & 15);
        return x;
    }
} it;
int n,m,f[1005][2],pl[1005],vst[1005],done[1005],cnt=0,cc=0,d[1005],v[1005],u[1005];
vector<int> g[1005],ans[1005];
void dfs(int x){
	if(!vst[x])cc--;
	done[x]=1,vst[x]=1,ans[cnt].push_back(x);
	random_shuffle(g[x].begin(),g[x].end());
	if(rand()%10){
		for(int i=1;i<g[x].size();i++)if(!vst[g[x][i]]){swap(g[x][i],g[x][0]);break;}
	}
	for(int y:g[x]){
		if(!done[y]){
			dfs(y);
			return ;
		}
	}
}
void Print(){
	cout<<1<<endl;
	int nd=(n+5)/6;
	for(int i=1;i<=cnt;i++){
		int o=min(nd-cnt+i-1,(int)ans[i].size());
		for(int j=0;j<o;j++){
			cout<<"1 "<<ans[i].back()<<'\n';
			nd--,ans[i].pop_back();
		}
		if(ans[i].size()){
			cout<<ans[i].size()<<' ';
			for(int j:ans[i])cout<<j<<' ';
			puts(""),nd--;
		}
	}
	exit(0);
}
vector<int> tg[1005];
int main(){
	srand(time(0));
	n=it,m=it,cc=n;
	for(int i=1,x,y;i<=m;i++){
		x=it,y=it;
		g[x].push_back(y),g[y].push_back(x);
		d[x]++,d[y]++;
	}
	for(int i=1;i<=n;i++)tg[i]=g[i];
	vector<int> a;
	for(int i=1;i<=n;i++){
		int mn=1e9,mnp=0;
		for(int j=1;j<=n;j++){
			if(d[j]<mn&&!u[j])mn=d[j],mnp=j;
		}
		if(!v[mnp]){
			a.push_back(mnp);
			for(int j:g[mnp])v[j]=1;
		}
		for(int j:g[mnp])d[j]--;
		u[mnp]=1;
		if(a.size()==n/3){
			cout<<2<<endl;
			for(int i:a)cout<<i<<' ';
			puts("");
			exit(0);
		}
	}
	while(cnt!=(n+5)/6){
		for(int i=1;i<=n;i++)pl[i]=i;
		random_shuffle(pl+1,pl+n+1);
		for(int o=1;o<=n;o++){
			int i=pl[o];
			if(!vst[i]){
				memset(done,0,sizeof(done));
				++cnt;
				dfs(i);
				if(cc==0)Print();
				if(cnt==(n+5)/6)break;
			}
		}
	}
	return 0;
}