#include <bits/stdc++.h>
using namespace std;
string imp = "Impossible\n";
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
clock_t startTime;
double getCurrentTime() {
  return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
const int N = 1e5 + 1e3;
long long MOD = 1e9 + 7;
vector<int> adj[N];
int lev[N], par[N];
void dfs(int u) {
  for (auto i : adj[u]) {
    if (i == par[u]) continue;
    if (lev[i] == 0) {
      lev[i] = lev[u] + 1;
      par[i] = u;
      dfs(i);
    } else if (lev[i] < lev[u]) {
      vector<int> ans;
      ans.push_back(u);
      int v = u;
      while (v != i) {
        v = par[v];
        ans.push_back(v);
      }
      cout << "2\n" << (int)ans.size() << "\n";
      for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
      }
      exit(0);
    }
  }
}
int main() {
  startTime = clock();
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int tests = 1;
  while (tests--) {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
      int u, v;
      cin >> u >> v;
      if (u > k || v > k) continue;
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
    for (int i = 1; i <= k; i++) {
      if (lev[i] == 0) {
        lev[i] = 1;
        dfs(i);
      }
    }
    vector<int> ans[2];
    for (int i = 1; i <= k; i++) {
      if (lev[i] & 1)
        ans[1].push_back(i);
      else
        ans[0].push_back(i);
    }
    k = (k + 1) / 2;
    if ((int)ans[0].size() < (int)ans[1].size()) {
      swap(ans[0], ans[1]);
    }
    cout << "1\n";
    for (int i = 0; i < k; i++) cout << ans[0][i] << " ";
  }
  return 0;
}
