#include <bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
using namespace std;
const long double eps = 1e-7;
const int inf = 1000000010;
const long long INF = 10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 100010, LOG = 20;
int n, m, k, u, v, x, y, t, a, b, ans;
int par[MAXN];
int h[MAXN];
vector<int> G[MAXN], v0, v1;
void dfs(int node) {
  h[node] = h[par[node]] + 1;
  for (int v : G[node])
    if (v != par[node]) {
      if (!h[v])
        par[v] = node, dfs(v);
      else if (h[v] < h[node] && h[node] - h[v] + 1 <= k) {
        cout << "2\n" << h[node] - h[v] + 1 << '\n';
        while (node != par[v]) cout << node << ' ', node = par[node];
        exit(0);
      }
    }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> k;
  while (m--) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1);
  for (int i = 1; i <= n; i++)
    if (h[i] <= k) {
      if (h[i] & 1)
        v1.push_back(i);
      else
        v0.push_back(i);
    }
  if (v0.size() < v1.size()) v0.swap(v1);
  cout << "1\n";
  for (int i = 0; i < (k + 1) / 2; i++) cout << v0[i] << ' ';
  return 0;
}
