#include <bits/stdc++.h>
using namespace std;
const long long INFLL = LLONG_MAX;
const int INF = INT_MAX;
const long long MAXLL = 0x3f3f3f3f3f3f3f3f;
const int MAX = 0x3f3f3f3f;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T> >;
template <class T>
void sort(vector<T>& v) {
  sort(v.begin(), v.end());
}
template <class T, class U>
void sort(vector<T>& v, U func) {
  sort(v.begin(), v.end(), func);
}
template <class T>
int lb_index(vector<T>& v, T k) {
  return lower_bound(v.begin(), v.end(), k) - v.begin();
}
template <class T>
int ub_index(vector<T>& v, T k) {
  return upper_bound(v.begin(), v.end(), k) - v.begin();
}
int n, m, k;
vector<int> v[100002];
vector<int> st(100002, -1), et(100002, -1);
vector<int> dep(100002, -1);
vector<int> par(100002, -1);
int tim;
int cycle = 100002;
int ccs = -1;
void dfs(int u, int p) {
  if (p == -1)
    dep[u] = 0;
  else
    dep[u] = dep[p] + 1;
  par[u] = p;
  st[u] = tim++;
  for (auto i : v[u]) {
    if (p == i) continue;
    if (st[i] == -1) {
      dfs(i, u);
    } else if (et[i] == -1) {
      if (cycle > dep[u] - dep[i]) {
        ccs = u;
        cycle = dep[u] - dep[i] + 1;
      }
    }
  }
  et[u] = tim;
}
void solve() {
  cin >> n >> m >> k;
  while (m--) {
    int l, r;
    cin >> l >> r;
    v[l].emplace_back(r);
    v[r].emplace_back(l);
  }
  dfs(1, -1);
  if (cycle <= k) {
    cout << 2 << "\n" << cycle << endl;
    int u = ccs;
    for (int i = 0; i < cycle; i++) {
      cout << u << ' ';
      u = par[u];
    }
    return;
  }
  cout << "1\n";
  vector<int> valid(100002);
  vector<int> ans;
  min_heap<pair<int, int> > pq;
  vector<int> temp(100002);
  for (int i = 0; i < n; i++) {
    temp[i + 1] = v[i + 1].size();
    pq.emplace(temp[i + 1], i + 1);
  }
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (!valid[u])
      ans.emplace_back(u);
    else
      continue;
    valid[u] = 1;
    for (int i : v[u]) {
      for (int j : v[i]) {
        temp[j]--;
        if (!valid[j]) pq.emplace(temp[j], j);
      }
      valid[i] = 1;
    }
  }
  for (int i = 0; i < ((k + 1) >> 1); i++) {
    cout << ans[i] << ' ';
  }
}
int main() {
  ios::sync_with_stdio(0);
  int numberofsubtestcases = 1;
  while (numberofsubtestcases--) {
    solve();
  }
}
