#include <bits/stdc++.h>
using namespace std;
int n, m, h[100005], cnt, deep[100005], prt[100005], B, sta[100005], tot, num;
bool flag = 0;
bool vis[100005], vst[100005];
vector<int> ans;
struct Edge {
  int to, next;
} w[400005];
void add(int x, int y) {
  w[++cnt] = (Edge){y, h[x]};
  h[x] = cnt;
}
void dfs(int x, int fa) {
  vis[x] = 1;
  deep[x] = deep[fa] + 1;
  prt[x] = fa;
  for (int i = h[x]; i; i = w[i].next) {
    int to = w[i].to;
    if (to == fa) continue;
    if (!vis[to])
      dfs(to, x);
    else if (!flag) {
      if (deep[x] - deep[to] + 1 >= B) {
        flag = 1;
        int now = x;
        while (now != to) sta[++tot] = now, now = prt[now];
        sta[++tot] = now;
      }
    }
  }
  if (!vst[x] && num < B) {
    num++;
    ans.push_back(x);
    for (int i = h[x]; i; i = w[i].next) vst[w[i].to] = 1;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  B = ceil(sqrt(n));
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    add(x, y);
    add(y, x);
  }
  dfs(1, 0);
  if (flag) {
    puts("2");
    printf("%d\n", tot);
    for (int i = 1; i <= tot; i++) printf("%d ", sta[i]);
  } else {
    puts("1");
    sort(ans.begin(), ans.end());
    for (int i = 0; i < B; i++) printf("%d ", ans[i]);
  }
}
