#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n, m, dfn[maxn], low[maxn], S[maxn], top, cnt, head[maxn], tot, col, deg[maxn], vis[maxn], visn[maxn], vism[maxn], visq[maxn];
queue<int> Q;
struct edge {
	int v, pre;
}e[maxn << 1];
void add(int u, int v) {
	e[++ tot].v = v;
	e[tot].pre = head[u];
	head[u] = tot;
}
vector<int> belong[maxn], vecn, vec[maxn], VEC[maxn], ansn;
vector<pair<int, int>> ans;
void check(int x, int y) {
	VEC[x].push_back(y);
}
void tarjan(int now, int fa) {
	dfn[now] = low[now] = ++ cnt;
	S[++ top] = now;
	for(int i = head[now];i;i = e[i].pre) {
		int v = e[i].v;
		if(vis[v]) continue;
		if(!dfn[v]) {
			tarjan(v, now);
			low[now] = min(low[now], low[v]);
			if(low[v] >= dfn[now]) {
				++ col;
				belong[col].push_back(now);
				check(now, col);
				vec[col + n].push_back(now);
				while(1) {
					int t = S[top];
					check(t, col);
					belong[col].push_back(t);
					vec[col + n].push_back(t);
					top --;
					if(t == v) break;
				}
			}
		}
		else if(v != fa) low[now] = min(low[now], dfn[v]);
	}
}
void dfs2(int now, int ID, int fa) {
	vism[now] = 1;
	vecn.push_back(now);
	for(int i = head[now];i;i = e[i].pre) {
		int v = e[i].v;
		if(v == fa || vism[v] || !visq[v]) continue;
		dfs2(v, ID, now);
	}
}
void dfs(int now, int fa) {
	visn[now] = 1;
	for(int v : vec[now]) {
		if(v == fa) continue;
		dfs(v, now);
	}
	if(now <= n) return;
	vecn.clear();
	for(int v : vec[now]) {
		visq[v] = 1;
	}
	if(!fa) {
		for(int v : vec[now]) {
			fa = v;
			ansn.push_back(v);
			break;
			
		}
	}
	dfs2(fa, now, fa);
	for(int i = 1;i < vecn.size();i++) {
		ans.push_back(make_pair(1, (i & 1) ? vecn[i] : vecn[i] + n));
	}
	ans.push_back(make_pair(1, vecn[1] + n));
	if(vecn.size() & 1) ans.push_back(make_pair(1, vecn.back()));
	else ans.push_back(make_pair(1, vecn.back() + n));
	for(int v : vec[now]) vism[v] = visq[v] = 0;
}
int main() {
//	freopen("A.in", "r", stdin);
//	freopen("my.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1, u, v;i <= m;i++) {
		cin >> u >> v;
		add(u, v), add(v, u);
		deg[u] ++, deg[v] ++;
	}
	for(int i = 1;i <= n;i++) if(deg[i] & 1) Q.push(i);
	while(!Q.empty()) {
		int t = Q.front();
		Q.pop();
		if(vis[t]) continue;
		if(deg[t] % 2 == 0) continue;
		ans.push_back(make_pair(1, t));
		vis[t] = 1;
		for(int i = head[t];i;i = e[i].pre) {
			int v = e[i].v;
			if(vis[v]) continue;
			deg[v] --;
			if(deg[v] & 1) Q.push(v);
		}
	}
	ans.push_back(make_pair(2, 0));
	for(int i = 1;i <= n;i++) {
		deg[i] = 0;
		if(vis[i]) continue;
		if(!dfn[i]) tarjan(i, 0);
	}
	for(int i = 1;i <= col;i++) {
		if(visn[i + n]) continue;
		dfs(i + n, 0);
	} 
	for(pair<int, int> t : ans) vism[t.second] = 1;
	for(int i = 1;i <= n;i++) if(vis[i]) ans.push_back(make_pair(1, i));
	for(int x : ansn) ans.push_back(make_pair(1, x));
	cout << 0 << " " << ans.size() << '\n';
	for(pair<int, int> t : ans) {
		if(t.first == 2) cout << 2 << '\n';
		else cout << t.first << " " << t.second << '\n';
	}
}