#include <bits/stdc++.h>
using namespace std;
int poz[100002], n, m, k;
vector<int> e, c, G[100002], s, tree[2];
void dfs(int x, int cul = 0) {
  poz[x] = s.size();
  tree[cul].push_back(x);
  s.push_back(x);
  int mx = -1;
  for (auto it : G[x]) {
    if (poz[it] != -1 && poz[x] - poz[it] > 1) mx = max(mx, poz[it]);
  }
  if (mx != -1 && c.empty()) {
    for (int i = mx; i <= poz[x]; i++) c.push_back(s[i]);
    return;
  }
  for (auto it : G[x])
    if (poz[it] == -1) dfs(it, 1 - cul);
  s.pop_back();
}
int main() {
  cin >> n >> m >> k;
  while (m--) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  memset(poz, -1, sizeof(poz));
  dfs(3);
  if (c.empty()) {
    if (tree[0].size() < tree[1].size()) swap(tree[0], tree[1]);
    cout << "1\n";
    for (int i = 0; i < (k + 1) / 2; i++) cout << tree[0][i] << " ";
  } else {
    if (c.size() <= k) {
      cout << "2\n" << c.size() << "\n";
      for (int i : c) cout << i << " ";
    } else {
      cout << "1\n";
      for (int i = 0; i < (k + 1) / 2; i++) cout << c[i * 2] << " ";
    }
  }
  return 0;
}
