#include<bits/extc++.h>
#include<bits/stdc++.h>
//#pragma GCC optimize(2)
//本代码含有小众情感元素，建议满 18 周岁后观看
#ifdef __unix__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#else
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#endif
#define debug fprintf(stderr,"Tomoyo after ~It's a wonderful life!~\n")
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define Inf (int)INFINITY
#define inf 0x3f3f3f3f
#define pb push_back
#define ll long long
#define endl '\n'
#define y second
#define x first
using namespace std;
const int N=6e5+10;
void read(){};
template<class T1,class ...T2>
inline void read(T1& ret,T2&... rest){
	ret=0;char c=getchar();bool f=false;
	while(c<'0'||c>'9')f=c=='-',c=getchar();
	while(c>='0'&&c<='9')ret=ret*10+c-'0',c=getchar();
	f&&(ret=-ret),read(rest...);
}
#define cin(...) read(__VA_ARGS__)
template<class T>
inline void print(T x){
	static int s[35],t=0;
	bool f=x<0;if(f)x=-x;
	do s[t++]=x%10,x/=10;while(x);
	f&&putchar('-');while(t)putchar(s[--t]+'0');
}
set<int>nxt[N];
vector<pii>ans;
vector<int>stk,rt,t[N];
int n,m,tmp,flg,tot,cnt,dfn[N],low[N],r[N];
void op(int u){
	ans.pb({1,u});
	if(u==153816)cout<<tmp<<endl,exit(0);
}
void work(int u){
	if(!(nxt[u].size()&1))return;
	vector<int>tmp;
	for(int v:nxt[u])tmp.pb(v),nxt[v].erase(u);
	op(u),nxt[u].clear();
	for(int v:tmp)work(v);
}
void Tarjan(int u,int fa){
	low[u]=dfn[u]=++tot,stk.pb(u);
	for(int v:nxt[u])if(v^fa){
		if(!dfn[v]){
			Tarjan(v,u),low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				t[++cnt].pb(u),t[u].pb(cnt);
				while(stk.back()!=u)
					t[cnt].pb(stk.back()),t[stk.back()].pb(cnt),stk.pop_back();
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
void dfs(int u,int fa){
	for(int v:t[u])if(v^fa)dfs(v,u);
	if(u>n){
//		assert(t[u][0]==fa);
		tmp=t[u].size();
		if(r[fa]){
			if(t[u].size()&1){
				for(int i=0;i+1<(int)(t[u].size());i++)op(t[u][i]+(i&1)*n);
				op(t[u][0]+n),op(t[u].back()+n),op(t[u].back());
			}
			else for(int i=0;i<(int)(t[u].size());i++)op(t[u][i]+(i&1)*n);
		}
		else{
			for(int i=1;i<(int)(t[u].size());i++)op(t[u][i]+(i&1)*n);
			op(t[u][1]),op(t[u].back()+(t[u].size()&1)*n);
		}
	}
}
int main(){
	cin(n,m),cnt=n;
	for(int i=1,u,v;i<=m;i++)
		cin(u,v),nxt[u].insert(v),nxt[v].insert(u);
	for(int u=1;u<=n;u++)work(u);
	for(int u=1;u<=n;u++)if(nxt[u].size())flg=1;
	if(!flg){
		print(0),putchar(' '),print(ans.size()),putchar(endl);
		for(pii p:ans)print(p.x),putchar(' '),print(p.y),putchar(endl);
		return 0;
	}
	ans.pb({2,0});
	for(int u=1;u<=n;u++){
		if(!nxt[u].size())op(u);
		else if(!dfn[u])rt.pb(u),r[u]=1,Tarjan(u,0);
	}
	for(int u:rt)dfs(u,0);
	print(0),putchar(' '),print(ans.size()),putchar(endl);
	for(pii p:ans){
		print(p.x);if(p.y)putchar(' '),print(p.y);
		putchar(endl);
	}
	return 0;
}