#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
using namespace std;

using vi = vector<int>;

constexpr int N = 3e5 + 9;
int n, m, deg[N];
bool iq[N], dl[N], vis[N];
vi g[N];

int dfn[N], low[N], dfc, stk[N], tp;

int ct;
vi dcc[N];

vector<string> as;

IL void re_1 (int x) {
  as.eb("1 " + to_string(x));
}

IL void re_2 () {
  as.eb("2");
}

IL void report () {
  cout << 0 << ' ' << as.size() << '\n';
  for (auto s : as) {
    cout << s << '\n';
  }
}

IL void dfs (int u) {
  dfn[u] = low[u] = ++dfc;
  stk[++tp] = u;
  for (int v : g[u]) {
    if (dl[v]) {
      continue;
    }
    if (!dfn[v]) {
      dfs(v);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        ++ct;
        dcc[ct].eb(u);
        ++deg[u];
        while (1) {
          int t = stk[tp--];
          dcc[ct].eb(t);
          ++deg[t];
          if (t == v) {
            break;
          }
        }
      }
    } else {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  L (i, 1, m) {
    int u, v;
    cin >> u >> v;
    g[u].eb(v);
    g[v].eb(u);
    ++deg[u];
    ++deg[v];
  }
  queue<int> q;
  L (i, 1, n) {
    if (!deg[i]) {
      q.push(i);
      iq[i] = 1;
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    iq[u] = 0;
    if (deg[u] & 1) {
      re_1(u);
      for (int v : g[u]) {
        if (!dl[v] && !iq[v] && ((--deg[v]) & 1)) {
          q.push(v);
        }
      }
    }
  }
  memset(deg, 0, (n + 1) << 2);
  L (i, 1, n) {
    if (!dl[i] && !dfn[i]) {
      dfs(i);
    }
  }
  if (!dfc) {
    report();
    return 0;
  }
  re_2();
  L (i, 1, ct) {
    auto &q = dcc[i];
    auto it = find_if(q.begin(), q.end(), [] (auto x) {
      return deg[x] > 1;
    });
    rotate(q.begin(), it, q.end());
    int o = q.size();
    assert(o > 1);
    L (j, 1, o - 1) {
      re_1(q[j] + (j & 1 ? n : 0));
      vis[q[j]] = 1;
    }
    re_1(q[1]);
    re_1(q[o - 1] + (o & 1 ? n : 0));
    for (int v : q) {
      --deg[v];
    }
  }
  L (i, 1, n) {
    if (!vis[i]) {
      re_1(i);
    }
  }
  report();
}
// I love WHQ!