#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dep[N];
vector<int> G[N], stk, cyc, a[2];
bool dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  a[dep[u] & 1].push_back(u);
  stk.push_back(u);
  int sz = 1e9;
  for (int v : G[u]) {
    if (v != fa && dep[v]) sz = min(sz, dep[u] - dep[v] + 1);
  }
  if (sz < 1e9) {
    int j = stk.size() - 1;
    while (sz--) cyc.push_back(stk[j--]);
    return true;
  }
  for (int v : G[u]) {
    if (!dep[v]) {
      if (dfs(v, u)) return true;
    }
  }
  stk.pop_back();
  return false;
}
int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1, 0);
  int tmp = (k + 1) / 2;
  if (m == n - 1) {
    printf("1\n");
    if (a[0].size() < tmp) swap(a[0], a[1]);
    for (int i = 0; i < tmp; i++) printf("%d ", a[0][i]);
    printf("\n");
    return 0;
  }
  if (cyc.size() <= k) {
    printf("2\n");
    printf("%d\n", cyc.size());
    for (int x : cyc) printf("%d ", x);
    printf("\n");
  } else {
    printf("1\n");
    for (int i = 0; i < cyc.size() && tmp; i += 2) {
      printf("%d ", cyc[i]);
      tmp--;
    }
    printf("\n");
  }
  return 0;
}
