#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 7;
vector<long long> v[N];
long long vis[N], prt[N], bip[N], cs, ce;
void dfs(long long ver, long long par) {
  bip[ver] = (!bip[par]);
  vis[ver] = 1;
  prt[ver] = par;
  for (auto it : v[ver]) {
    if (vis[it] == 2 || it == par) continue;
    if (vis[it] == 1) {
      cs = it;
      ce = ver;
      break;
    }
    dfs(it, ver);
  }
  vis[ver] = 2;
}
int32_t main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long n, m, k;
  cin >> n >> m >> k;
  for (long long i = (long long)(1); i <= (long long)(m); i++) {
    long long x, y;
    cin >> x >> y;
    if (x > k || y > k) continue;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  for (long long i = (long long)(1); i <= (long long)(k); i++) {
    if (vis[i]) continue;
    dfs(i, 0);
  }
  if (cs) {
    cout << 2 << "\n";
    vector<long long> ans;
    while (cs != ce) {
      ans.push_back(ce);
      ce = prt[ce];
    }
    ans.push_back(ce);
    cout << ans.size() << "\n";
    for (auto it : ans) cout << it << " ";
  } else {
    cout << 1 << "\n";
    long long kk = k / 2 + k % 2;
    long long tmp = count(bip + 1, bip + k + 1, 0);
    if (tmp >= kk) {
      for (long long i = (long long)(1); i <= (long long)(k); i++) {
        if (kk > 0 && bip[i] == 0) {
          cout << i << " ";
          kk--;
        }
      }
    } else {
      for (long long i = (long long)(1); i <= (long long)(k); i++) {
        if (kk > 0 && bip[i]) {
          cout << i << " ";
          kk--;
        }
      }
    }
  }
}
