#include <bits/stdc++.h>
using namespace std;
const int mx = 200050;
int vis[mx];
vector<int> vec[mx];
vector<int> ob[2];
vector<int> nodes, ans;
int st;
int ttt;
void dfs(int u, int from, int lv) {
  ob[lv].push_back(u);
  vis[u] = ttt;
  ttt++;
  nodes.push_back(u);
  int i, v, mxx, l = vec[u].size();
  mxx = 0;
  for (i = 0; i < l; i++) {
    v = vec[u][i];
    if (v == from) continue;
    if (vis[v] > mxx) {
      mxx = vis[v];
      st = v;
    }
  }
  for (i = 0; i < l && st == 0; i++) {
    v = vec[u][i];
    if (v == from) continue;
    assert(vis[v] == -1);
    dfs(v, u, lv ^ 1);
  }
  if (st == 0) nodes.pop_back();
}
int main() {
  int n, m, i, j, k, u, v, p, q;
  scanf("%d %d %d", &n, &m, &k);
  for (i = 0; i < m; i++) {
    scanf("%d %d", &u, &v);
    vec[u].push_back(v);
    vec[v].push_back(u);
  }
  st = 0;
  memset(vis, -1, sizeof(vis));
  ttt = 1;
  dfs(1, -1, 0);
  q = (k + 1) / 2;
  if (st == 0) {
    p = ob[0].size();
    printf("1\n");
    if (p >= q) {
      for (i = 0; i < q; i++) {
        printf("%d ", ob[0][i]);
      }
      printf("\n");
    } else {
      for (i = 0; i < q; i++) {
        printf("%d ", ob[1][i]);
      }
      printf("\n");
    }
    return 0;
  }
  int l = nodes.size();
  bool ok = 0;
  for (i = 0; i < l; i++) {
    if (nodes[i] == st) ok = 1;
    if (ok) ans.push_back(nodes[i]);
  }
  l = ans.size();
  if (l <= k) {
    printf("2\n");
    printf("%d\n", l);
    for (i = 0; i < l; i++) {
      printf("%d ", ans[i]);
    }
    printf("\n");
  } else {
    printf("1\n");
    for (i = 0; q--; i += 2) {
      assert(i < (int)ans.size());
      printf("%d ", ans[i]);
    }
    printf("\n");
  }
  return 0;
}
