#include<bits/stdc++.h>
const int maxn = 3e5 + 10, maxN = maxn * 2;
int n, m, N;
std::vector<int> qr;
std::vector<int> G[maxn], E[maxN];
bool vis[maxn];
int deg[maxn];
int dfn[maxn], low[maxn], stk[maxn], top, dt;
void dfs(int u) {
    dfn[u] = low[u] = ++dt, stk[++top] = u;
    for (int v : G[u]) {
        if (vis[v]) continue;
        if (! dfn[v]) {
            dfs(v);
            low[u] = std::min(low[u], low[v]);
            if (dfn[u] == low[v]) {
                N++;
                for (int t = 0; t != v; ) {
                    t = stk[top--];
                    E[t].push_back(N), E[N].push_back(t);
                }
                E[u].push_back(N), E[N].push_back(u);
            }
        } else low[u] = std::min(low[u], dfn[v]);
    }
}
void solve(int u, int fa) {
    for (int v : E[u]) v != fa && (solve(v, u), 1);
    if (u > n) {
        std::vector<int> P;
        for (int i = 0, cnt = 0; cnt < 2; cnt += E[u][i] == fa, (++i) %= E[u].size())
            cnt == 1 && E[u][i] != fa && (P.push_back(E[u][i]), 1);
        int op = 0;
        for (int v : P) qr.push_back(v + op * n), op ^= 1;
        qr.push_back(P.front() + n), qr.push_back(P.back() + op * n);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y), G[y].push_back(x);
        deg[x]++, deg[y]++;
    }
    std::vector<int> q1;
    std::queue<int> q;
    for (int i = 1; i <= n; i++) deg[i] <= 1 && (q.push(i), 1);
    while (! q.empty()) {
        int u = q.front(); q.pop();
        assert(u != 140183);
        ! vis[u] && (q1.push_back(u), vis[u] = 1);
        if (! deg[u]) continue;
        qr.push_back(u);
        deg[u]--;
        for (int v : G[u]) if (deg[v]) (--deg[v]) <= 1 && (q.push(v), 1);
    }
    qr.push_back(0);
    for (int x : q1) qr.push_back(x);
    N = n;
    for (int i = 1; i <= n; i++) {
        if (vis[i] || dfn[i]) continue;
        top = 0, dfs(i);
        solve(i, 0);
        qr.push_back(i);
    }
    printf("0 %zu\n", qr.size());
    for (int x : qr) ! x ? puts("2") : printf("1 %d\n", x);
    return 0;
}