#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=3e5+5;
int n,m,deg[N];
vector<int> e[N],edge[N],g[N<<1];
bool vis[N];
vector<int> ans;
void del(int x){
	ans.pb(x),vis[x]=true,deg[x]=0;
	for(auto y:e[x]) if(!vis[y]) deg[y]^=1;
	for(auto y:e[x]) if(!vis[y]&&deg[y]) del(y);
}
int dfn[N],low[N],tot,stk[N],top,scc;
void tarjan(int x){
	dfn[x]=low[x]=++tot,stk[++top]=x;
	for(auto y:edge[x]){
		if(!dfn[y]){
			tarjan(y),low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				int t; ++scc;
				do t=stk[top--],g[scc].pb(t),g[t].pb(scc); while(t!=y);
				g[x].pb(scc),g[scc].pb(x);
			}
		}else low[x]=min(low[x],dfn[y]);
	}
}
int pos[N];
void work(int x,int fa){
	for(auto y:g[x]) if(y!=fa) work(y,x);
	if(x<=n){
		if(!fa) ans.pb(x);
		return vis[x]=true,void();
	}
	int p=0;
	for(int i=0;i<g[x].size();++i) if(g[x][i]==fa){ p=i; break; }
	for(int i=0;i<g[x].size();++i) pos[i]=g[x][(p+i)%g[x].size()];
	for(int i=1;i<g[x].size();++i) ans.pb(pos[i]+((i&1)?0:n));
	ans.pb(pos[g[x].size()-1]+((g[x].size()-1&1)?n:0)),ans.pb(pos[1]+n);
}
int main(){
	scanf("%d%d",&n,&m),scc=n;
	for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),e[u].pb(v),e[v].pb(u),deg[u]^=1,deg[v]^=1;
	for(int i=1;i<=n;++i) if(!vis[i]&&deg[i]) del(i);
	ans.pb(0);
	for(int x=1;x<=n;++x) if(!vis[x]) for(auto y:e[x]) if(!vis[y]) edge[x].pb(y);
	for(int i=1;i<=n;++i){
		vis[i]=false;
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=n;++i) if(!vis[i]) work(i,0);
	printf("0 %d\n",(int)ans.size());
	for(auto x:ans){
		if(!x) puts("2");
		else printf("1 %d\n",x);
	}
	return 0;
}