#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= f;
}
template <class T>
T gcd(T a, T b) {
  return !b ? a : gcd(b, a % b);
}
template <class T>
inline void umin(T &x, T y) {
  x = x < y ? x : y;
}
template <class T>
inline void umax(T &x, T y) {
  x = x > y ? x : y;
}
mt19937 R(chrono::system_clock().now().time_since_epoch().count());
const int N = 4e5 + 11;
int n, m, lim, fa[N], dep[N], dp[N];
vector<int> e[N], b;
void dfs(int u, int Fa, int Dep) {
  fa[u] = Fa;
  dep[u] = Dep;
  for (int v : e[u])
    if (v != Fa && !dep[v])
      dfs(v, u, Dep + 1);
    else if (v != Fa && dep[v] < dep[u] && dep[u] - dep[v] + 1 >= lim) {
      vector<int> a;
      for (int x = u;; x = fa[x]) {
        a.push_back(x);
        if (x == v) break;
      }
      puts("2");
      printf("%d\n", ((int)a.size()));
      for (int x : a) printf("%d ", x);
      exit(0);
    }
}
void dfs1(int u) {
  for (int v : e[u])
    if (v != fa[u] && dep[v] == dep[u] + 1) dfs1(v), umin(dp[u], dp[v]);
  if (dp[u] > dep[u] && ((int)b.size()) < lim)
    b.push_back(u), dp[u] = dep[u] - (lim - 1) + 1;
}
int main() {
  read(n);
  read(m);
  for (register int i = (1); i <= (m); i++) {
    int u, v;
    read(u);
    read(v);
    e[u].push_back(v);
    e[v].push_back(u);
  }
  lim = sqrt(n);
  if (lim * lim != n) lim++;
  dfs(1, 0, 1);
  for (register int i = (1); i <= (n); i++) dp[i] = n + 1;
  dfs1(1);
  assert(((int)b.size()) == lim);
  puts("1");
  for (int x : b) printf("%d ", x);
  return 0;
}
