#include<bits/stdc++.h>
using namespace std;
int n,m;
set<int> edge[300005];
vector<int> ans;
vector<int> e1[600005];
int tot;
int dfn[300005],low[300005],cnt;
stack<int> st;
int vis[300005];
void dfs1(int x){
	ans.push_back(x);
	set<int> S;swap(S,edge[x]);
	for(int y:S)edge[y].erase(x);
	for(int y:S)if(edge[y].size()&1)dfs1(y);
}
void addedge(int x,int y){
	e1[x].push_back(y);
	e1[y].push_back(x);
}
void Tarjan(int x){
	dfn[x]=low[x]=++cnt;
	st.push(x);
	for(int y:edge[x])
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				tot++;
				int z;
				do{
					z=st.top();st.pop();
					addedge(z,tot);
				}while(z!=y);
				addedge(x,tot);
			}
		}else low[x]=min(low[x],dfn[y]);
}
void dfs2(int x,int f){
	for(int y:e1[x])if(y!=f)dfs2(y,x);
	if(x>n){
		int p=0;
		for(int i=0;i<e1[x].size();i++)if(e1[x][i]==f){p=i;break;}
		int flag=1;
		for(int i=p+1;i<e1[x].size();i++,flag^=1)
			if(flag)ans.push_back(e1[x][i]);
			else ans.push_back(e1[x][i]+n);
		for(int i=0;i<p;i++,flag^=1)
			if(flag)ans.push_back(e1[x][i]);
			else ans.push_back(e1[x][i]+n);
		flag=0;
		for(int i=p+1;i<e1[x].size();i++,flag^=1)
			if(flag)ans.push_back(e1[x][i]);
			else ans.push_back(e1[x][i]+n);
		for(int i=0;i<p;i++,flag^=1)
			if(flag)ans.push_back(e1[x][i]);
			else ans.push_back(e1[x][i]+n);
	}else vis[x]=1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		edge[x].insert(y);
		edge[y].insert(x);
	}
	for(int i=1;i<=n;i++)if(edge[i].size()&1)dfs1(i);
	ans.push_back(0);
	tot=n;
	for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
	for(int i=1;i<=n;i++)if(!vis[i]&&!e1[i].empty())dfs2(i,0),ans.push_back(i);
	printf("0 %d\n",(int)ans.size());
	for(int x:ans)if(x>0)printf("1 %d\n",x);else puts("2");
	return 0;
}