#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 100 * 1000 + 10;
long long n, m, dis[MAXN], par[MAXN], ans = -1, V = -1;
vector<long long> adj[MAXN], vec;
set<pair<long long, long long> > s;
long long k;
bool mark[MAXN];
void indp() {
  long long d[MAXN];
  for (long long i = 0; i < n; i++) d[i] = adj[i].size(), s.insert({d[i], i});
  while (!s.empty()) {
    auto p = s.begin();
    long long de = p->first, v = p->second;
    s.erase({de, v});
    if (mark[v]) continue;
    vec.push_back(v);
    mark[v] = 1;
    for (auto u : adj[v])
      if (!mark[u]) {
        mark[u] = 1;
        s.erase({d[u], u});
        for (auto x : adj[u])
          if (!mark[x]) {
            auto it = s.lower_bound({d[x], x});
            s.erase(it);
            d[x]--;
            s.insert({d[x], x});
          }
      }
  }
  return;
}
void dfs(long long v) {
  mark[v] = 1;
  for (auto u : adj[v]) {
    if (!mark[u])
      par[u] = v, dis[u] = dis[v] + 1, dfs(u);
    else {
      long long t = abs(dis[v] - dis[u]) + 1;
      if (t <= k) ans = u, V = v;
    }
  }
  return;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> k;
  for (long long i = 0; i < m; i++) {
    long long u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v), adj[v].push_back(u);
  }
  indp();
  long long sz = vec.size();
  if (sz >= (k + 1) / 2) {
    cout << 1 << endl;
    for (long long i = 0; i < (k + 1) / 2; i++) cout << vec[i] + 1 << ' ';
    return cout << endl << endl, 0;
    ;
  }
  for (long long i = 0; i < MAXN; i++) mark[i] = 0;
  par[0] = -1;
  dfs(0);
  if (ans != -1) {
    cout << 2 << endl << abs(dis[V] - dis[ans]) + 1 << endl;
    long long cur = ans;
    while (cur != par[V]) {
      cout << cur + 1 << ' ';
      cur = par[cur];
    }
    cout << endl;
  }
  return 0;
}
