#include <bits/stdc++.h>
using namespace std;
vector<int> edge[1212121];
int par[121212][20], depth[121212];
int S[212121], E[212121];
void up(int &a, int b) {
  for (int i = 0; i < 20; i++) {
    if ((1 << i) & b) a = par[a][i];
  }
}
int get_lca(int x, int y) {
  if (depth[x] > depth[y]) up(x, depth[x] - depth[y]);
  if (depth[x] < depth[y]) up(y, depth[y] - depth[x]);
  if (x == y) return x;
  for (int i = 19; i >= 0; i--) {
    if (par[x][i] == par[y][i]) continue;
    x = par[x][i];
    y = par[y][i];
  }
  return par[x][0];
}
int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  int i, j;
  for (i = 0; i < m; i++) {
    int s, e;
    scanf("%d%d", &s, &e);
    edge[s].push_back(e);
    edge[e].push_back(s);
    S[i] = s;
    E[i] = e;
  }
  deque<int> Q;
  Q.push_back(1);
  for (i = 1; i <= n; i++)
    for (j = 0; j < 20; j++) par[i][j] = -1;
  par[1][0] = -1;
  depth[1] = 0;
  while (!Q.empty()) {
    int now = Q.front();
    Q.pop_front();
    for (int nxt : edge[now]) {
      if (nxt == 1 || par[nxt][0] != -1) continue;
      par[nxt][0] = now;
      for (i = 0; par[nxt][i] != -1; i++) par[nxt][i + 1] = par[par[nxt][i]][i];
      depth[nxt] = depth[now] + 1;
      Q.push_back(nxt);
    }
  }
  int needInde = (k + 1) / 2;
  int mn = -1, mns, mne;
  for (i = 0; i < m; i++) {
    int s = S[i], e = E[i];
    if (par[s][0] == e || par[e][0] == s) continue;
    int lca = get_lca(s, e);
    int size = depth[s] - depth[lca] + depth[e] - depth[lca] + 1;
    if (mn == -1 || mn > size) {
      mn = size, mns = s, mne = e;
    }
  }
  if (mn == -1) {
    int cnt = 0;
    for (i = 1; i <= n; i++) {
      if (depth[i] % 2 == 0) cnt++;
    }
    printf("1\n");
    if (cnt >= needInde) {
      cnt = 0;
      for (i = 1; i <= n; i++) {
        if (depth[i] % 2 == 0) {
          printf("%d ", i);
          cnt++;
        }
        if (cnt == needInde) break;
      }
    } else {
      cnt = 0;
      for (i = 1; i <= n; i++) {
        if (depth[i] % 2 == 1) {
          printf("%d ", i);
          cnt++;
        }
        if (cnt == needInde) break;
      }
    }
    return 0;
  }
  deque<int> list;
  int s = mns, e = mne;
  int lca = get_lca(s, e);
  int now = s;
  while (now != lca) {
    list.push_back(now);
    now = par[now][0];
  }
  list.push_back(lca);
  now = e;
  while (now != lca) {
    list.push_front(now);
    now = par[now][0];
  }
  if (list.size() <= k) {
    printf("2\n");
    printf("%d\n", list.size());
    for (i = 0; i < list.size(); i++) printf("%d ", list[i]);
    return 0;
  } else {
    printf("1\n");
    int cnt = 0;
    for (i = 0; i < list.size(); i += 2) {
      printf("%d ", list[i]);
      cnt++;
      if (cnt == needInde) break;
    }
  }
  return 0;
}
