考慮把每個字符串的前 \(k\) 位和后 \(k\) 位看成點，字符串看成邊，那么一個字符串前綴后綴至少有一個是相似群體的前綴后綴，看成這條邊的兩個端點至少有一個被選中。

那么這就變成了一個最小點覆蓋問題。

考慮匈牙利算法算出答案，然后考慮如何構造答案。

考慮右邊沒有被匹配的點，選中這些點向左邊連的點，因此這個點本身就不用被選中，考慮左邊剛剛被選中的點，它們在右邊匹配的點就不用選了，那么它們在右邊匹配的點就進入右邊沒有被匹配的點相同的流程，如此遞歸下去，那么左邊便利到的點就會被選中，右邊被遍歷到的點就不會被選中。

如此便可以構造出選中的點，然后再分配字符串到集合即可。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

const int maxn = 1e6+114;
const int base = 1145141;
int vis[maxn],match[maxn];
vector<int> edge[maxn],fedge[maxn];
map<int,int> road[2][maxn];
int ans;
int fm[maxn];
bool hungary(int u){
	for(int v:edge[u]){
		if(vis[v]==1) continue;
		vis[v]=1;
		if(match[v]==0||hungary(match[v])==true){
			match[v]=u;
			fm[u]=v;
			return true;
		}
	}
	return false;
}

int pre[maxn],suf[maxn];

int n,k,cnt;
map<int,int> f;
map<int,int> p[2];
vector<int> chifan[2];
int use[maxn][2];

vector<int> answer[2];
map<int,int> pos[2];

int op[maxn][2];
vector<int> OUT[maxn][2];
void dfs(int u,int type){
	if(op[u][type]==1) return ;
	op[u][type]=1;
	if(type==0){
		dfs(fm[u],1);
	}
	else{
		for(int nxt:fedge[u]){
			if(nxt!=match[u]){
				dfs(nxt,0);
			}
		}
	}
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<k;j++){
			pre[i]=pre[i]*base+s[j];
		}
		for(int j=s.size()-1;j>=s.size()-k&&j<s.size();j--){
			suf[i]=suf[i]*base+s[j];
		}
		if(f[pre[i]]==0){
			f[pre[i]]=++cnt;
		}
		if(p[0][f[pre[i]]]==0)
			chifan[0].push_back(f[pre[i]]),p[0][f[pre[i]]]=1;
		if(f[suf[i]]==0){
			f[suf[i]]=++cnt;
		}
		if(p[1][f[suf[i]]]==0)
			chifan[1].push_back(f[suf[i]]),p[1][f[suf[i]]]=1;
		edge[f[pre[i]]].push_back(f[suf[i]]),fedge[f[suf[i]]].push_back(f[pre[i]]);
	}
	for(int i:chifan[0]){
		memset(vis,0,sizeof(vis));
		if(hungary(i)==true) ans++;
	}
	for(int i:chifan[1]){
		if(match[i]==0){
			dfs(i,1);
		}
	}
	for(int i=1;i<=n;i++){
		if(op[f[pre[i]]][0]==1){
			OUT[f[pre[i]]][0].push_back(i);
		}
		else if(op[f[suf[i]]][1]==0){
			OUT[f[suf[i]]][1].push_back(i);
		}
	}
	cout<<ans<<'\n';
	for(int i:chifan[0]){
		if(op[i][0]==1){
			cout<<OUT[i][0].size()<<' ';
			for(int j:OUT[i][0]) cout<<j<<' ';
			cout<<'\n';
		}
	}
	for(int i:chifan[1]){
		if(op[i][1]==0){
			cout<<OUT[i][1].size()<<' ';
			for(int j:OUT[i][1]) cout<<j<<' ';
			cout<<'\n';
		}
	}
	return 0;
}