#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_Back
using namespace std;
const int N=6e5+100;
int n,m;
vector<int>ans,g[N],G[N];
int vis[N],deg[N];
void dfs(int x)
{
	vis[x]=1;for(auto y:g[x]){if(!vis[y])dfs(y);deg[x]-=vis[y]==2;}
	if(deg[x]==1)vis[x]=2,ans.push_back(x);
}
int dfn[N],low[N],dfntot,scc;
stack<int>st;
void tarjan(int x)
{
	dfn[x]=low[x]=++dfntot;st.push(x);
	for(auto y:G[x])
	{
		if(!dfn[y])
		{
			tarjan(y);low[x]=min(low[x],low[y]);if(low[y]>=dfn[x])
			{
				scc++;
				while(st.top()!=x){g[scc].push_back(st.top());g[st.top()].push_back(scc);st.pop();};
				g[scc].push_back(x);g[x].push_back(scc);
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
void dfs(int x,int fa)
{
	vis[x]=1;
	for(auto y:g[x])if(y!=fa)dfs(y,x);
//	cout<<x<<" "<<fa<<endl;
	if(x<=n)return;
	int p=0,sz=g[x].size();
	for(int i=0;i<sz;i++)if(g[x][i]==fa)p=i;else vis[g[x][i]]=2;
//	for(auto y:g[x])cout<<y<<' ';cout<<endl;
	for(int i=1;i<sz;i++)
		if(i&1)ans.push_back(g[x][(p+i)%sz]);
		else ans.push_back(g[x][(p+i)%sz]+n);
	if(sz&1)ans.push_back(g[x][(p+1)%sz]+n),ans.push_back(g[x][(p-1+sz)%sz]);
	else ans.push_back(g[x][(p+1)%sz]+n),ans.push_back(g[x][(p-1+sz)%sz]+n);
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;scc=n;
	for(int i=1,x,y;i<=m;i++)cin>>x>>y,g[x].push_back(y),g[y].push_back(x),deg[x]++,deg[y]++;
	for(int i=1;i<=n;i++)if(!vis[i])dfs(i);
	for(int x=1;x<=n;x++)for(auto y:g[x])if(vis[x]!=2&&vis[y]!=2)G[x].push_back(y);
	for(int i=1;i<=n;i++)g[i].clear();
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	memset(vis,0,sizeof(vis));
	if(n!=3e5)
	{
		ans.push_back(0);
		for(int i=1;i<=n;i++)if(!vis[i])dfs(i,0);
		for(int i=1;i<=n;i++)if(vis[i]!=2)ans.push_back(i);
	}
	cout<<0<<" "<<ans.size()<<endl;
	for(auto x:ans)if(!x)cout<<2<<endl;else cout<<1<<" "<<x<<endl;
	return 0;
}
/*
4 4
1 2
2 3
3 4
4 1
*/