#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  while (a != 0 && b != 0) {
    if (a > b)
      a %= b;
    else
      b %= a;
  }
  return max(a, b);
}
void boost() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
int n, m, k;
vector<vector<int>> vec(100005);
vector<int> vis(100005), level(100005), parent(100005);
void dfs(int i) {
  vis[i] = 1;
  for (auto j : vec[i]) {
    if (j == parent[i]) continue;
    if (level[j] == 0) {
      level[j] = level[i] + 1;
      parent[j] = i;
      dfs(j);
    } else {
      cout << "2\n";
      vector<int> ans;
      int temp = i;
      while (temp != j) {
        ans.push_back(temp);
        temp = parent[temp];
      }
      ans.push_back(j);
      cout << ans.size() << endl;
      for (auto it : ans) cout << it << ' ';
      exit(0);
    }
  }
}
int main() {
  boost();
  int i, j, a, b;
  cin >> n >> m >> k;
  for (i = 0; i < m; i++) {
    cin >> a >> b;
    if (a > k || b > k) continue;
    vec[a].push_back(b);
    vec[b].push_back(a);
  }
  for (i = 1; i < k + 1; i++) {
    if (vis[i] == 0) {
      level[i] = 1;
      dfs(i);
    }
  }
  cout << "1\n";
  vector<int> o, e;
  for (i = 1; i < k + 1; i++) {
    if (level[i] % 2)
      o.push_back(i);
    else
      e.push_back(i);
  }
  if (o.size() > e.size())
    for (i = 0; i < (k + 1) / 2; i++) cout << o[i] << ' ';
  else
    for (i = 0; i < (k + 1) / 2; i++) cout << e[i] << ' ';
}
