#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;

int n, m, tp, tot;
int d[N], ct[N], vs[N], st[N], bel[N];

set<int> g[N];
vector<int> t[N];
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();
		int v = *g[u].begin();
		res.eb(mp(1, u));
		g[v].era(u), g[u].clear();
		if (g[v].size() == 1) q.push(v);
	}
}

void dfs(int u, int fa) {
	vs[u] = 1;
	for (int v : g[u]) {
		if (!vs[v]) st[++tp] = u, dfs(v, u);
		else {
			if (v == fa || u < v) continue;
			st[++tp] = u, tot++;
			// cout << u << '\n';
			// for (int i = 1; i <= tp; i++) cout << st[i] << ' '; cout << '\n';
			while (tp && st[tp] != v) {
				int w = st[tp];
				if (!bel[w]) bel[w] = tot;
				c[tot].eb(w), tp--;
			}
			c[tot].eb(v), tp--;
			if (!bel[v]) bel[v] = tot;
		}
	}
}

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++) {
		for (int j : c[i]) {
			if (ct[j] > 1) {
				d[i]++;
				if (bel[j] != i) t[bel[j]].eb(i), t[i].eb(bel[j]);
			}
		}
		if (d[i] <= 1) q.push(i);
	}
	while (!q.empty()) {
		int i = q.front(); q.pop();
		int fl = 0, sz = c[i].size();
		for (int j = 0; j < sz - 1; j++)
			res.eb(mp(1, c[i][j] + fl * n)), fl ^= 1;
		res.eb(mp(1, c[i][sz - 2] + fl * n));
		if (sz & 1) fl ^= 1;
		res.eb(mp(1, c[i][0] + fl * n));
		int flg = 0;
		for (int j : t[i]) {
			d[j]--;
			if (!d[j]) q.push(j), flg = 1;
		}
		if (!flg) res.eb(mp(1, c[i][sz - 1]));
	}
}

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);
	doit(), res.eb(mp(2, 0)), dohim();
	for (auto [x, y] : res) {
		if (x == 2) break;
		res.eb(mp(1, y));
	}
	cout << 0 << ' ' << res.size() << '\n';
	for (auto [x, y] : res) 
		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;
}