#include <bits/stdc++.h>
int n, m, k;
std::vector<std::vector<int>> al;
std::vector<bool> vis;
std::vector<int> p;
std::vector<int> d;
std::vector<int> near;
void dfs(int v, int depth, int parent) {
  vis[v] = true;
  p[v] = parent;
  d[v] = depth;
  for (auto w : al[v])
    if (w != parent) {
      if (vis[w] && d[w] < d[v]) {
        if (near[w] == -1) {
          near[w] = v;
        } else {
          if (d[near[w]] > d[v]) near[w] = v;
        }
      } else if (!vis[w]) {
        dfs(w, depth + 1, v);
      }
    }
}
int main() {
  std::cin >> n >> m >> k;
  vis = std::vector<bool>(n, false);
  p = std::vector<int>(n);
  d = std::vector<int>(n, 0);
  near = std::vector<int>(n, -1);
  al = std::vector<std::vector<int>>(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    std::cin >> u >> v;
    u--, v--;
    al[u].push_back(v);
    al[v].push_back(u);
  }
  dfs(0, 0, -1);
  int sc = -1;
  for (int v = 0; v < n; v++) {
    if (near[v] != -1) {
      if (sc == -1) {
        sc = v;
      } else {
        if ((d[near[sc]] - d[sc]) > (d[near[v]] - d[v])) sc = v;
      }
    }
  }
  if (sc == -1) {
    std::cout << 1 << "\n";
    int odd = 0;
    for (auto di : d) odd += di % 2;
    int to_use = odd >= (k / 2 + k % 2);
    int cnt = 0;
    for (int v = 0; v < n; v++)
      if (d[v] % 2 == to_use) {
        std::cout << v + 1 << " ";
        cnt++;
        if (cnt == (k / 2 + k % 2)) {
          std::cout << "\n";
          return 0;
        }
      }
  } else {
    std::vector<int> in_cycle;
    in_cycle.push_back(sc);
    for (int v = near[sc]; v != sc; v = p[v]) in_cycle.push_back(v);
    if (in_cycle.size() > k) {
      std::cout << "1\n";
      int cnt = 0;
      for (int i = 0; i < in_cycle.size(); i++)
        if (i % 2 == 0) {
          std::cout << in_cycle[i] + 1 << " ";
          cnt++;
          if (cnt == (k / 2 + k % 2)) break;
        }
      std::cout << "\n";
    } else {
      std::cout << "2\n";
      std::cout << in_cycle.size() << "\n";
      for (auto v : in_cycle) std::cout << v + 1 << " ";
      std::cout << "\n";
    }
  }
  return 0;
}
