#include <bits/stdc++.h>
#define eb emplace_back
#define pb pop_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define ins insert
#define era erase

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;

const int N = 3e5 + 300;
const int M = 5e5 + 500;

int n, m, tp;
int dfc, tot, low[N], dfn[N], st[N];
int ct[N], in[N], bel[N], fa[N];
pi e[M];

set<int> g[N << 1];
vector<int> c[N];
vector<pi> res;

void doit() {
	queue<int> q;
	for (int i = 1; i <= n; i++) 
		if (g[i].size() & 1) q.push(i);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (g[u].size() & 1 ^ 1) continue;
		res.eb(mp(1, u));
		for (int v : g[u]) {
			g[v].era(u);
			if (g[v].size() & 1) q.push(v);
		}
		g[u].clear();
	}
}

void dfs(int u, int f) {
	st[++tp] = u, dfn[u] = low[u] = ++dfc;
	for (int v : g[u]) {
		if (v == f) continue;
		if (dfn[v]) low[u] = min(low[u], dfn[v]);
		else {
			dfs(v, u), low[u] = min(low[u], low[v]);
			if (low[v] == dfn[u]) {
				tot++;
				for (int x = 0; x != v; tp--) {
					x = st[tp];
					c[tot].eb(st[tp]);
				}
				c[tot].eb(u);
				for (int i : c[tot]) bel[i] = tot;
			}
		}
	}
}

void dohim() {
	for (int i = 1; i <= n; i++) 
		if (!dfn[i]) dfs(i, 0);
	for (int i = 1; i <= tot; i++)
		for (int j : c[i]) ct[j]++;
	queue<int> q;
	for (int i = 1; i <= tot; i++) in[i] = 0;
	for (int i = 1; i <= tot; i++) 
		for (int j : c[i]) {
			if (bel[j] != i) assert(!fa[i]);
			if (ct[j] > 1 && bel[j] != i)
				fa[i] = bel[j], in[bel[j]]++;
		}
	// for (int i = 1; i <= tot; i++, cout << '\n')
		// for (int j : c[i]) cout << j << ' ';
	// for (int i = 1; i <= tot; i++) cout << fa[i] << '\n';
	for (int i = 1; i <= tot; i++)	
		if (!in[i]) q.push(i);
	while (!q.empty()) {
		int i = q.front(); q.pop();
		// res.eb(mp(1, 1000 + i));
		int p = -1, sz = c[i].size();
		for (int u : c[i]) 
			if (ct[u] >= 2) p = u;
		// cout << i << ' ' << p << '\n';
		if (p != -1 && c[i][0] != p) {
			int pos;
			for (int j = 1; j < sz; j++)
				if (c[i][j] == p) pos = j;
			vector<int> tc; tc.eb(p);
			for (int j = pos + 1; j < sz; j++) tc.eb(c[i][j]);
			for (int j = 0; j < pos; j++) tc.eb(c[i][j]);
			c[i] = tc;
		}
		int fl = 0;
		for (int j = 1; j < sz; j++)
			res.eb(mp(1, c[i][j] + fl * n)), fl ^= 1;
		res.eb(mp(1, c[i][sz - 1] + fl * n));
		if (sz & 1) fl ^= 1;
		res.eb(mp(1, c[i][1] + fl * n));
		in[fa[i]]--;
		if (fa[i] && !in[fa[i]]) q.push(fa[i]);
		for (int u : c[i]) ct[u]--;
	}
}

void solve() {
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++)
		cin >> u >> v, g[u].ins(v), g[v].ins(u), e[i] = mp(u, v);
	doit(), res.eb(mp(2, 0)), dohim();
	for (int i = 1; i <= n; i++) g[i].clear();
	for (int i = 1; i <= m; i++) {
		int u = e[i].fi, v = e[i].se;
		g[u].ins(v), g[v].ins(u);
	}
	for (pi _ : res) {
		int op = _.fi, x = _.se;
		if (op == 2) {
			for (int i = 1; i <= n; i++)
				for (int j : g[i]) g[i + n].ins(j + n);
			for (int i = 1; i <= n; i++)
				g[i].ins(i + n), g[i + n].ins(i);
		} else {
			for (int y : g[x]) g[y].era(x);
			g[x].clear();
		}
	}
	for (int i = 1; i <= n; i++) 
		if (g[i].size()) res.eb(mp(1, i));
	cout << 0 << ' ' << res.size() << '\n';
	for (auto _ : res) {
		int x = _.fi, y = _.se;
		if (x == 1) cout << 1 << ' ' << y << '\n';
		else cout << 2 << '\n';
	}
}

bool Med;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	#ifdef FILE
		freopen("1.in", "r", stdin);
		freopen("1.out", "w", stdout);
	#endif
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}