#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;;
int n,m;
vector<int>E[N],G[N],ans;
int deg[N],dfn[N],low[N],tot,top,st[N],dl[N],cnt;
void an(int x){ans.push_back(x);}
void del(int x){
	an(x);
	dl[x]=1;deg[x]=0;
	for(int v:E[x])if(!dl[v])deg[v]^=1;
	for(int v:E[x])if(deg[v])del(v);
}
void dfs(int u){
	dfn[u]=low[u]=++tot;st[++top]=u;
	for(int v:G[u]){
		if(!dfn[v]){
			dfs(v);
			if(low[v]>=dfn[u]){
				cnt++;
				while(st[top]!=v){
					E[cnt].push_back(st[top]);
					E[st[top]].push_back(cnt);
					top--;
				}
				E[cnt].push_back(v);
				E[v].push_back(cnt);
				E[cnt].push_back(u);
				E[u].push_back(cnt);
			}
			else low[u]=min(low[u],low[v]);
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
int vis[N],a[N];
void sol(int u,int fa){
	vis[u]=1;
	for(int v:E[u])if(v!=fa)sol(v,u);
	if(u<=n){
		if(!fa)an(u);
		return;
	}
	int p=0,m=E[u].size();
	for(int i=0;i<m;i++)if(E[u][i]==fa)p=i;
	for(int i=0;i<m;i++)a[i]=E[u][(p+i)%m];
	for(int i=1;i<m;i++)an(a[i]+((i&1)^1)*n);
	an(a[m-1]+((m-1)&1)*n);an(a[1]+n);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		E[x].push_back(y);E[y].push_back(x);
		deg[x]^=1;deg[y]^=1;
	}
	for(int i=1;i<=n;i++)if(deg[i]&1)del(i);
	an(0);
	for(int i=1;i<=n;i++){
		if(!dl[i]){
			for(int j:E[i]){
				if(!dl[j])G[i].push_back(j),G[j].push_back(i);
			}
		}
	}
	for(int i=1;i<=n;i++)E[i].clear();
	cnt=n;
	for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
	for(int i=1;i<=n;i++)if(!vis[i])sol(i,0);
	printf("0 %d\n",ans.size());
	for(int i:ans){
		if(i==0)printf("2\n");
		else printf("1 %d\n",i);
	}
	return 0;
}