_Kamisato_Ayaka_ @ 2024-11-12 16:58:04
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e6 + 10;
int n,m,idx = 1,head[MAXN << 1],cur;
int low[MAXN],dfn[MAXN],color[MAXN],sccnt;
bool vis[MAXN];
stack < int > st;
vector < int > Ans[MAXN];
struct node{
int v,nxt;
}edge[MAXN << 1];
inline void add(int u,int v)
{
edge[idx].v = v;
edge[idx].nxt = head[u];
head[u] = idx ++;
}
inline void tarjan(int u,int fa)
{
low[u] = dfn[u] = ++ cur;
vis[u] = 1;
st.push(u);
for(int i = head[u];i != -1;i = edge[i].nxt)
{
int v = edge[i].v;
if(i == (fa ^ 1)) continue;
if(!dfn[v])
{
tarjan(v,i);
low[u] = min(low[u],low[v]);
}
else if(vis[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u])
{
sccnt ++;
while(st.top() != u)
{
color[st.top()] = sccnt;
vis[st.top()] = 0;
Ans[sccnt].push_back(tmp);
st.pop();
}
st.pop();
}
}
signed main()
{
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
memset(head,-1,sizeof(head));
for(int i = 1;i <= m;i ++)
{
int u,v;
cin >> u >> v;
if(u != v) add(u,v),add(v,u);
}
for(int i = 1;i <= n;i ++)
{
if(!dfn[i]) tarjan(i,0);
}
cout << sccnt << endl;
for(int i = 1;i <= sccnt;i ++)
{
cout << Ans[i].size() << " ";
for(int j = 0;j < Ans[i].size();j ++)
cout << Ans[i][j] << " ";
cout << endl;
}
return 0;
}