#include <bits/stdc++.h>
using namespace std;
vector<bool> pertenece;
vector<vector<int> > gr;
vector<int> pos;
deque<int> ciclo;
vector<int> candidatos;
vector<pair<int, int> > edge;
vector<int> color[2];
int n, m, k;
void dfs(int u) {
  pos[u] = candidatos.size();
  color[pos[u] % 2].push_back(u);
  candidatos.push_back(u);
  for (int v : gr[u]) {
    if (pos[v] == -1)
      dfs(v);
    else {
      if (ciclo.empty() && pos[u] - pos[v] > 1) {
        for (int i = pos[v]; i <= pos[u]; i++) {
          ciclo.push_back(candidatos[i]);
          pertenece[candidatos[i]] = 1;
        }
      }
    }
  }
  candidatos.pop_back();
}
int main() {
  scanf("%d", &n);
  scanf("%d", &m);
  scanf("%d", &k);
  gr.assign(n + 1, vector<int>());
  pos.assign(n + 1, -1);
  int a, b;
  edge.reserve(m);
  pertenece.assign(n + 1, false);
  while (m--) {
    scanf("%d", &a);
    scanf("%d", &b);
    gr[a].push_back(b);
    gr[b].push_back(a);
    edge.push_back(pair<int, int>(a, b));
  }
  dfs(1);
  if (ciclo.empty()) {
    if (color[1].size() > color[0].size()) swap(color[0], color[1]);
    printf("1\n");
    for (int i = 0; i < (k + 1) / 2; i++) printf("%d ", color[0][i]);
  } else {
    for (auto p : edge) {
      if (pertenece[p.first] && pertenece[p.second] &&
          abs(pos[p.first] - pos[p.second]) != 1) {
        while (ciclo.front() != p.first && ciclo.front() != p.second) {
          pertenece[ciclo.front()] = 0;
          ciclo.pop_front();
        }
        while (ciclo.back() != p.first && ciclo.back() != p.second) {
          pertenece[ciclo.back()] = 0;
          ciclo.pop_back();
        }
      }
    }
    if (ciclo.size() <= k) {
      printf("2\n%d\n", ciclo.size());
      for (int i : ciclo) printf("%d ", i);
    } else {
      printf("1\n");
      for (int i = 0; i < k; i += 2) printf("%d ", ciclo[i]);
    }
  }
  return 0;
}
