#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, g[maxn][2], deg[maxn], vis[maxn], visn[maxn], vism[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];
vector<pair<int, int>> ans;
void check(int x, int y) {
	if(!g[x][0]) g[x][0] = y;
	else g[x][1] = 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);
				while(1) {
					int t = S[top];
					check(t, col);
					belong[col].push_back(t);
					top --;
					if(t == v) break;
				}
			}
		}
		else if(v != fa) low[now] = min(low[now], dfn[v]);
	}
}
void dfs(int now, int ID, int fa) {
	vecn.push_back(now);
	vism[now] = 1;
	for(int i = head[now];i;i = e[i].pre) {
		int v = e[i].v;
		if(v == fa || vism[v]) continue;
		if(g[v][0] != ID && g[v][1] != ID) continue;
		dfs(v, ID, now);
	}
}
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);
		}
	}
//	return 0;
	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 <= n;i++) {
		if(vis[i]) continue;
		if(g[i][1]) vec[g[i][0]].push_back(g[i][1]), vec[g[i][1]].push_back(g[i][0]), deg[g[i][0]] ++, deg[g[i][1]] ++;
	}
	for(int i = 1;i <= col;i++) if(deg[i] == 0) Q.push(i);
	while(!Q.empty()) {
		int t = Q.front(), rt = 0;
		visn[t] = 1;
		vecn.clear();
		Q.pop();
		for(int x : belong[t]) {
			if(!rt) rt = x;
			if(!g[x][1]) continue;
			int P = t ^ g[x][0] ^ g[x][1];
			if(!visn[P]) rt = x;
		}
		dfs(rt, t, rt);
		for(int x : belong[t]) vism[x] = 0;
		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[t]) {
			deg[v] --;
			if(!deg[v]) Q.push(v);
		}
	}
	for(pair<int, int> t : ans) vism[t.second] = 1;
	for(int i = 1;i <= n;i++) if(!vism[i] || vis[i]) ans.push_back(make_pair(1, i));
	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';
	}
}