#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
#define pii pair<int,int> 
#define fi first
#define se second
#define mkp(x,y) make_pair(x,y)
vector<int>ed[maxn],lp[maxn],bel[maxn];
int del[maxn],deg[maxn],n,m,vis[maxn],dfn[maxn],sta[maxn],tp,cdfn;
int clp,nd[maxn],siz[maxn];
void dfs(int x,int pre){
	dfn[x]=++cdfn,sta[++tp]=x;
	for(auto v:ed[x]){
		if(del[v]||v==pre)continue;
		if(!dfn[v])dfs(v,x);
		else if(dfn[v]<dfn[x]){
			clp++;
			for(int i=tp;;i--){//O(m)
				lp[clp].push_back(sta[i]);
				bel[sta[i]].push_back(clp);
				siz[sta[i]]++;
				if(sta[i]==v)break;
			}
		}
	}
	tp--;
}
vector<pii>ans;
int main(){
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		ed[u].push_back(v);
		ed[v].push_back(u);
		deg[u]++,deg[v]++;
	}
	queue<int>Q;
	for(int i=1;i<=n;i++)if(deg[i]&1)Q.push(i);
	while(!Q.empty()){
		int now=Q.front();
		Q.pop();
		if(del[now]||!(deg[now]&1))continue;
		ans.push_back(mkp(1,now));
		del[now]=1;
		for(auto v:ed[now])deg[v]--,Q.push(v);
	}
	for(int i=1;i<=n;i++)deg[i]=0;
	for(int i=1;i<=n;i++){
		for(auto v:ed[i]){
			if(i<v&&!del[i]&&!del[v])deg[i]++,deg[v]++;
		}
	}
	for(int i=1;i<=n;i++)if(!deg[i])del[i]=1;
	/*for(int i=1;i<=n;i++)cout<<i<<" "<<i+n<<"\n";
	for(int i=1;i<=n;i++){
		for(auto v:ed[i]){
			if(i<v&&!del[i]&&!del[v])cout<<i<<" "<<v<<"\n",cout<<i+n<<" "<<v+n<<"\n";
		}
	}*/
	ans.push_back(mkp(2,-1));
	for(int i=1;i<=n;i++)if(del[i])ans.push_back(mkp(1,i));
	for(int i=1;i<=n;i++)if(!del[i]&&!dfn[i])dfs(i,0);
//	cout<<clp<<endl;
	for(int i=1;i<=n;i++){
		if(bel[i].size()>1)for(auto v:bel[i])nd[v]++;
	}
	for(int i=1;i<=clp;i++)if(nd[i]<=1)Q.push(i);
	while(!Q.empty()){
		int V=Q.front();
		Q.pop();
		if(vis[V])continue;
		vis[V]=1;
		int S=-1;
		if(nd[V]==0)S=0;
		else for(int i=0;i<lp[V].size();i++)if(siz[lp[V][i]]>1)S=i;
		vector<int>R;
		R.push_back(lp[V][S]);
		for(int i=S+1;i<lp[V].size();i++)R.push_back(lp[V][i]);
		for(int i=0;i<S;i++)R.push_back(lp[V][i]);
		for(int i=1,o=1;i<R.size();i++,o^=1){
			if(o)ans.push_back(mkp(1,R[i]));
			else ans.push_back(mkp(1,R[i]+n));
		}
		if(R.size()>1)ans.push_back(mkp(1,R[1]+n));
		if(R.size()>2){
			if((R.size()-1)&1)ans.push_back(mkp(1,R[R.size()-1]+n));
			else ans.push_back(mkp(1,R[R.size()-1]));
		}
		if(siz[R[0]]==1){
			ans.push_back(mkp(1,R[0]));
		} else {
			siz[R[0]]--;
			if(siz[R[0]]==1){
				for(auto v:bel[R[0]]){
					nd[v]--;
					if(nd[v]<1&&!vis[v])Q.push(v);
				}
			}
		}
	}
	for(int i=1;i<=clp;i++)assert(vis[i]==1);
	cout<<0<<" "<<ans.size()<<"\n";
	for(auto v:ans){
		if(v.fi==1)cout<<v.fi<<" "<<v.se<<"\n";
		else cout<<v.fi<<"\n";
	}
	return 0;	
}
/*
8 10
1 2
2 4
1 4
3 4
3 5
5 6
3 6
3 7
3 8
7 8
*/