#include <bits/stdc++.h>
using namespace std;
vector<int> G[100005], v;
int n, m, k, sel[100005], pus, t[100005];
bool fnd[100005];
vector<int> bfs(int pl) {
  queue<int> q;
  q.push(pl);
  sel[1] = 1;
  t[1] = -1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (auto it : G[x]) {
      if (!sel[it]) {
        sel[it] = sel[x] + 1;
        t[it] = x;
        q.push(it);
      } else if (t[x] != it) {
        int y = it;
        vector<int> r1, r2;
        while (sel[x] > sel[y]) {
          r1.push_back(x);
          x = t[x];
        }
        while (sel[y] > sel[x]) {
          r2.push_back(y);
          y = t[y];
        }
        while (x != y) {
          r1.push_back(x);
          r2.push_back(y);
          x = t[x];
          y = t[y];
        }
        r1.push_back(x);
        reverse(r2.begin(), r2.end());
        for (auto it2 : r2) {
          r1.push_back(it2);
        }
        return r1;
      }
    }
  }
}
void dfs1(int x, int level) {
  fnd[x] = true;
  if (level % 2 == 0 && pus < (k + 1) / 2) {
    v.push_back(x);
    ++pus;
  }
  for (auto it : G[x]) {
    if (!fnd[it]) {
      dfs1(it, level + 1);
    }
  }
}
void dfs2(int x, int level) {
  fnd[x] = true;
  if (level % 2 == 1 && pus < (k + 1) / 2) {
    v.push_back(x);
    ++pus;
  }
  for (auto it : G[x]) {
    if (!fnd[it]) {
      dfs2(it, level + 1);
    }
  }
}
void find_shortest_cycle() {
  if (m == n - 1) {
    cout << 1 << '\n';
    dfs1(1, 1);
    if (v.size() < (k + 1) / 2) {
      for (int i = 1; i <= n; i++) {
        fnd[i] = false;
      }
      v.clear();
      pus = 0;
      dfs2(1, 1);
    }
    for (auto it : v) {
      cout << it << ' ';
    }
    return;
  }
  vector<int> cop = bfs(1);
  for (auto it : cop) {
    v.push_back(it);
  }
  if (v.size() <= k) {
    cout << 2 << '\n';
    cout << v.size() << '\n';
    for (auto it : v) {
      cout << it << ' ';
    }
    cout << '\n';
  } else {
    cout << 1 << '\n';
    int alese = 0;
    for (int i = 0; i < v.size() && alese < (k + 1) / 2; i++) {
      if (i % 2 == 0) {
        cout << v[i] << ' ';
        ++alese;
      }
    }
    cout << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  find_shortest_cycle();
  return 0;
}
