#include <bits/stdc++.h>
using namespace std;
vector<long long> a[100005], vis(100005, 0), tree[100005], lev[2];
long long n, m, k;
set<long long> v;
stack<long long> st;
void dfs(long long node, long long par) {
  vis[node] = 1;
  st.push(node);
  for (auto i : a[node])
    if (!vis[i] and v.find(i) != v.end()) {
      tree[node].push_back(i);
      tree[i].push_back(node);
      dfs(i, node);
    } else if (v.find(i) != v.end() and i != par) {
      cout << 2 << '\n';
      vector<long long> ans;
      while (!st.empty() and st.top() != i) {
        ans.push_back(st.top());
        st.pop();
      }
      ans.push_back(i);
      cout << (long long)ans.size() << '\n';
      for (auto i : ans) cout << i << " ";
      exit(0);
    }
  st.pop();
}
void dfs1(long long node, long long par, long long d) {
  lev[d].push_back(node);
  for (auto i : tree[node])
    if (i != par) {
      dfs1(i, node, 1 - d);
    }
}
void get_subgraph() {
  queue<long long> q;
  q.push(1);
  v.insert(1);
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();
    for (auto i : a[cur]) {
      if (v.find(i) == v.end()) {
        v.insert(i);
        q.push(i);
        if ((long long)v.size() == k) break;
      }
    }
    if ((long long)v.size() == k) break;
  }
}
void solve() {
  cin >> n >> m >> k;
  for (long long i = 0; i < m; i++) {
    long long x, y;
    cin >> x >> y;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  get_subgraph();
  dfs(1, -1);
  dfs1(1, -1, 0);
  long long req = (k + 1) / 2;
  cout << 1 << '\n';
  vector<long long> ans;
  if ((long long)lev[0].size() >= req)
    ans = lev[0];
  else
    ans = lev[1];
  for (long long i = 0; i < req; i++) cout << ans[i] << " ";
}
signed main() {
  long long TESTS = 1;
  while (TESTS--) {
    solve();
  }
  return 0;
}
