#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
vector<vector<int>> g;
bool hascycle = false;
int n, m, k;
vector<int> cycle, color;
vector<int> par, pre, vis;
void dfs(int i) {
  if (hascycle) return;
  vis[i] = 1;
  for (auto a : g[i]) {
    if (hascycle) return;
    if (vis[a] == 0) {
      color[a] = color[i] ^ 1;
      par[a] = i;
      dfs(a);
    } else if (par[i] != a) {
      queue<int> q;
      q.push(a);
      vector<int> v(n);
      while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto nx : g[cur]) {
          if (cur == a && nx == i) continue;
          if (!v[nx]) {
            pre[nx] = cur;
            if (nx == i) goto done;
            q.push(nx);
            v[nx] = 1;
          }
        }
      }
    done:
      cycle.push_back(i + 1);
      int nd = i;
      while (nd != a) {
        nd = pre[nd];
        cycle.push_back(nd + 1);
      }
      hascycle = true;
    }
  }
}
int main() {
  cin >> n >> m >> k;
  g.resize(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  par.resize(n);
  vis.resize(n);
  pre.resize(n);
  color.resize(n);
  dfs(0);
  if (hascycle) {
    if (cycle.size() <= k) {
      cout << 2 << endl << cycle.size() << endl;
      for (auto a : cycle) cout << a << " ";
    } else {
      cout << 1 << endl;
      int t = 0;
      for (int i = 0; i < cycle.size() && t < (k + 1) / 2; i += 2, t++)
        cout << cycle[i] << " ";
    }
  } else {
    vector<int> white, black;
    for (int i = 0; i < n; i++) {
      if (color[i] == 0)
        black.push_back(i);
      else
        white.push_back(i);
    }
    if (white.size() < black.size()) swap(white, black);
    int req = (k + 1) / 2;
    cout << 1 << endl;
    for (int i = 0; i < white.size(); i++) {
      if (req) {
        cout << white[i] + 1 << " ";
        req--;
      }
    }
  }
  return 0;
}
