#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, tot;
int ct[N], in[N], vs[N], st[N], bel[N], fa[N];
pi e[M];

set<int> g[N << 1];
vector<int> t[N], 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 fa) {
	vs[u] = 1, st[++tp] = u, in[u] = 1;
	for (int v : g[u]) {
		if (!vs[v]) dfs(v, u);
		else {
			if (v == fa || !in[v]) continue;
			tot++, c[tot].eb(v);
			for (int i = tp; i && st[i] != v; i--) {
				int w = st[i];
				if (!bel[w]) bel[w] = tot;
				c[tot].eb(w);
			}
			if (!bel[v]) bel[v] = tot;
		}
	}
	in[u] = 0, tp--;
}

void dohim() {
	for (int i = 1; i <= n; i++) 
		if (!vs[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 (ct[j] > 1) 
				if (bel[j] != i) t[fa[i] = bel[j]].eb(i), in[bel[j]]++;
	for (int i = 1; i <= tot; i++)
		if (!in[i]) q.push(i);
	while (!q.empty()) {
		int i = q.front(); q.pop();
		int p = -1, sz = c[i].size();
		for (int u : c[i]) 
			if (ct[u] > 2) p = u;
		if (p != -1 && p != c[i][0]) {
			cout << c[i][0] << ' ' << p << '\n';
			exit(0);
		}
		for (int j = 1; j < sz; j++)
			if (c[i][j] == p) swap(c[i][j], c[i][0]);
		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;
}