#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 300100;

int n, m, a[maxn];
bool vis[maxn];
vector<int> G1[maxn], G2[maxn], ans;

void dfs(int u) {
	vis[u] = 1;
	ans.pb(u);
	for (int v : G1[u]) {
		a[v] ^= 1;
	}
	for (int v : G1[u]) {
		if (!vis[v] && a[v]) {
			dfs(v);
		}
	}
}

int dfn[maxn], low[maxn], stk[maxn], top, nt, tim;

void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++tim;
	stk[++top] = u;
	for (int v : G2[u]) {
		if (v == fa) {
			continue;
		}
		if (!dfn[v]) {
			tarjan(v, u);
			if (low[v] >= dfn[u]) {
				++nt;
				while (1) {
					if (top < 0) {
						exit(0);
					}
					int x = stk[top--];
					G1[nt].pb(x);
					G1[x].pb(nt);
					if (x == v) {
						break;
					}
				}
				G1[nt].pb(u);
				G1[u].pb(nt);
			} else {
				low[u] = min(low[u], low[v]);
			}
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}
}

void dfs(int u, int fa) {
	vis[u] = 1;
	for (int v : G1[u]) {
		if (v == fa) {
			continue;
		}
		dfs(v, u);
	}
	if (u <= n) {
		if (fa == -1) {
			ans.pb(u);
		}
		return;
	}
	for (int i = 0; i < (int)G1[u].size(); ++i) {
		if (G1[u][i] == fa) {
			rotate(G1[u].begin(), G1[u].begin() + i, G1[u].end());
			break;
		}
	}
	for (int i = 1; i < (int)G1[u].size(); ++i) {
		ans.pb(G1[u][i] + ((i & 1) ? 0 : n));
	}
	ans.pb(G1[u][1] + n);
	ans.pb(G1[u].back() + ((G1[u].size() & 1) ? 0 : n));
}

void solve() {
	scanf("%d%d", &n, &m);
	while (m--) {
		int u, v;
		scanf("%d%d", &u, &v);
		G1[u].pb(v);
		G1[v].pb(u);
		a[u] ^= 1;
		a[v] ^= 1;
	}
	for (int i = 1; i <= n; ++i) {
		if (a[i] && !vis[i]) {
			dfs(i);
		}
	}
	for (int u = 1; u <= n; ++u) {
		for (int v : G1[u]) {
			if (!vis[u] && !vis[v]) {
				G2[u].pb(v);
			}
		}
		vector<int>().swap(G1[u]);
	}
	nt = n;
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) {
			tarjan(i, -1);
		}
	}
	ans.pb(0);
	mems(vis, 0);
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			dfs(i, -1);
		}
	}
	printf("0 %d\n", (int)ans.size());
	for (int i : ans) {
		if (i) {
			printf("1 %d\n", i);
		} else {
			puts("2");
		}
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}