#include<bits/stdc++.h>
using namespace std;using ll=long long;
int rd(int x=0,char c=getchar()){while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+(c^48),c=getchar();return x;}
const int N=3e5+5;
int n,m;
vector<int> E[N],G[N],path[N];;
int tot,fl[N];
int r[N],vis[N];
vector<int> op1,op2,bl[N];
int fa[N],dep[N];
void dfs(int u){
	dep[u]=dep[fa[u]]+1;
	for(int v:G[u]){
		if(v==fa[u])continue;
		if(dep[v]){
			if(dep[v]>dep[u])continue;
			path[++tot].push_back(u);
			while(path[tot].back()!=v)path[tot].push_back(fa[path[tot].back()]);
		}else fa[v]=u,dfs(v);
	}
}
int main(){
	n=rd(),m=rd();
	for(int i=1;i<=m;i++){
		int u=rd(),v=rd();
		E[u].push_back(v);
		E[v].push_back(u);
		r[u]++,r[v]++;
	}queue<int> q;
	for(int i=1;i<=n;i++)if(r[i]&1)q.push(i);
	while(q.size()){
		int u=q.front();q.pop();
		if(r[u]%2==0)continue;
		op1.push_back(u);vis[u]=1;
		for(int v:E[u]){
			r[v]--;
			if(r[v]&1&&!vis[v])q.push(v);
		}
	}if(op1.size()==n){
		printf("0 %d\n",(int)op1.size());
		for(int x:op1)printf("1 %d\n",x);
		return 0;
	}

	if(n<30000){


	for(int i=1;i<=n;i++)if(!vis[i]){
		r[i]=0;
		for(int j:E[i])if(!vis[j])G[i].push_back(j);
	}for(int i=1;i<=n;i++)if(vis[i])op2.push_back(i);
	for(int i=1;i<=n;i++)if(!dep[i])dfs(i);
	for(int i=1;i<=n;i++)for(int j:G[i])r[j]++;
	for(int i=1;i<=tot;i++){
		int c=0;
		for(int x:path[i])if(r[x]>2)c++;
		for(int x:path[i])
		bl[x].push_back(i);
		if(c<=1)q.push(i),fl[i]=1;
	}while(q.size()){
		int u=q.front();q.pop();
		int p=0,l=path[u].size();
		for(int i=0;i<l;i++)if(r[path[u][i]]>2)p=i;
		int nw=(p+1)%l;
		for(int i=0;i<l-1;i++){
			op2.push_back(path[u][nw]+(i&1)*n);
			nw=(nw+1)%l;
		}
		if(l&1){
			op2.push_back(path[u][(p-1+l)%l]);
			op2.push_back(path[u][(p+1)%l]+n);
			op2.push_back(path[u][p]+n);
		}else{
			op2.push_back(path[u][p]+n);
		}
		if(r[path[u][p]]>2){
			int w=path[u][p];
			for(int v:bl[w]){
				r[v]--;
				if(r[v]<=1&&!fl[v])q.push(v),fl[v]=1;
			}
		}

	}

	}
	printf("0 %d\n",(int)(op1.size()+op2.size())+1);
	for(int x:op1)printf("1 %d\n",x);
	puts("2");
	for(int x:op2)printf("1 %d\n",x);
	return 0;
}