#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
bool visited[N];
int n, m, k;
std::set<int> v[N];
vector<int> now, cycle;
int clr[N], pos[N];
bool done = 0;
std::vector<int> s;
void dfs(int node, int colour = 0, int parent = -1) {
  visited[node] = 1;
  clr[node] = colour;
  pos[node] = s.size();
  s.push_back(node);
  int h = -1;
  for (auto i : v[node]) {
    if (visited[i] == 1 and i != parent) {
      h = max(h, pos[i]);
    }
  }
  if (h != -1 and int(cycle.size()) == 0) {
    for (int i = h; i < int(s.size()); i++) cycle.push_back(s[i]);
    return;
  }
  for (auto i : v[node]) {
    if (visited[i] == 0) dfs(i, 1 - colour, node);
  }
  s.pop_back();
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin.exceptions(cin.failbit);
  cin >> n >> m >> k;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    v[x].insert(y);
    v[y].insert(x);
  }
  dfs(1);
  if (int(cycle.size()) == 0) {
    std::vector<int> one, zero;
    for (int i = 1; i <= n; i++)
      if (clr[i])
        one.push_back(i);
      else
        zero.push_back(i);
    cout << 1 << endl;
    if (int(one.size()) > int(zero.size())) {
      for (int i = 0; i < (k + 1) / 2; i++) cout << one[i] << " ";
    } else {
      for (int i = 0; i < (k + 1) / 2; i++) cout << zero[i] << " ";
    }
  } else if ((cycle.size()) <= k) {
    cout << 2 << endl << cycle.size() << endl;
    for (auto i : cycle) cout << i << " ";
  } else {
    int cnt = (k + 1) / 2;
    cout << 1 << endl;
    int ind = 0;
    while (cnt--) {
      cout << cycle[ind] << " ";
      ind += 2;
      ind %= int(cycle.size());
    }
  }
}
