#include <bits/stdc++.h>

constexpr int N = 300005;

int n, m, cnt;
struct Edge { int x, y; };
Edge edge[N * 2];
bool del[N * 2], vis[N * 2];
std::vector<int> graph1[N];
int deg1[N];

int go(int u, int e) {
    if (u == edge[e].x) return edge[e].y;
    if (u == edge[e].y) return edge[e].x;
    assert(false);
}

std::vector<int> ans;
void work(int u) {
    ans.push_back(u);
    deg1[u] = 0;
    for (int e : graph1[u]) {
        if (del[e]) continue;
        int v = go(u, e);
        deg1[v]--;
    }
    for (int e : graph1[u]) {
        if (del[e]) continue;
        del[e] = 1;
        int v = go(u, e);
        if (deg1[v] & 1) work(v);
    }
}

int deg2[N * 2];
std::vector<int> graph2[N * 2];
int dfn[N], low[N], tot, dfs_cnt;
std::stack<int> sta;
void tarjan(int u) {
    sta.push(u);
    low[u] = dfn[u] = ++dfs_cnt;
    for (int e : graph1[u]) {
        if (del[e]) continue;
        if (vis[e]) continue;
        vis[e] = 1;
        int v = go(u, e);
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                tot++;
                int x;
                do {
                    x = sta.top();
                    sta.pop();
                    deg2[x]++;
                    deg2[tot]++;
                    graph2[x].push_back(tot);
                    graph2[tot].push_back(x);
                }
                while (x != v);
                deg2[u]++;
                deg2[tot]++;
                graph2[u].push_back(tot);
                graph2[tot].push_back(u);
            }
        }
        else low[u] = std::min(low[u], dfn[v]);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edge[++cnt] = {x, y};
        graph1[x].push_back(cnt);
        graph1[y].push_back(cnt);
        deg1[x]++;
        deg1[y]++;
    }
    for (int i = 1; i <= n; i++) if (deg1[i] & 1) work(i);
    for (int i = 1; i <= n; i++) if (deg1[i] & 1) work(i);
    for (int i = 1; i <= n; i++) if (deg1[i] & 1) work(i);
    if (n >= 10000) {
        return 0;
    }
    ans.push_back(-1);
    tot = n;
    for (int i = 1; i <= n; i++) {
        if (deg1[i]) {
            if (!dfn[i]) tarjan(i);
        }
        else ans.push_back(i);
    }
    std::queue<int> que;
    for (int i = 1; i <= tot; i++) if (deg2[i] == 1) que.push(i);
    while (que.size()) {
        int u = que.front();
        que.pop();
        if (u > n) {
            int p = -1;
            for (int i = 0; i < graph2[u].size(); i++)
                if (deg2[graph2[u][i]] > 1) 
                    p = i;
            std::vector<int> cur;
            if (p >= 0) {
                for (int i = p; i < graph2[u].size(); i++) cur.push_back(graph2[u][i]);
                for (int i = 0; i < p; i++) cur.push_back(graph2[u][i]);
            }
            else cur = graph2[u];
            for (int i = 1; i < cur.size(); i++) ans.push_back(cur[i] + (i & 1) * n);
            ans.push_back(cur[1]);
            ans.push_back(cur.back() + (cur.size() & 1) * n);
            if (p == -1) ans.push_back(cur[0]);
        }
        for (int v : graph2[u]) 
            if (--deg2[v] == 1)
                que.push(v);
    }
    printf("%d %lu\n", 0, ans.size());
    for (int x : ans) {
        if (x < 0) puts("2");
        else printf("1 %d\n", x);
    }
    return 0;
}