#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
vector<long long> g[100010];
long long visited[100010], par[100010], dep[100010];
vector<long long> white, black;
vector<long long> cycle;
bool dfs(long long u, long long p, long long color) {
  par[u] = p;
  visited[u] = 1;
  if (color == 0)
    white.push_back(u);
  else
    black.push_back(u);
  long long val = -1, id = -1;
  for (auto x : g[u]) {
    if (visited[x] == 1 and x != p and dep[x] > val) {
      val = dep[x];
      id = x;
    }
  }
  if (id != -1) {
    long long cur = u;
    while (cur != id) {
      cycle.push_back(cur);
      cur = par[cur];
    }
    cycle.push_back(id);
    return true;
  }
  for (auto x : g[u]) {
    if (!visited[x]) {
      dep[x] = 1 + dep[u];
      if (dfs(x, u, color ^ 1)) return true;
    }
  }
  visited[u] = 2;
  return false;
}
void solve() {
  memset(dep, -1, sizeof dep);
  long long n, m, k;
  cin >> n >> m >> k;
  for (long long i = 0; i < m; ++i) {
    long long a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  dep[1] = 0;
  if (dfs(1, -1, 0)) {
    if (cycle.size() <= k) {
      cout << 2 << '\n';
      cout << cycle.size() << '\n';
      for (auto x : cycle) cout << x << " ";
    } else {
      cout << 1 << '\n';
      long long id = 0;
      for (long long i = 0; i < (k + 1) / 2; i++)
        cout << cycle[id] << " ", id += 2;
    }
  } else {
    if (white.size() < black.size()) swap(white, black);
    cout << 1 << '\n';
    for (long long i = 0; i < (k + 1) / 2; i++) cout << white[i] << " ";
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  long long t = 1;
  while (t--) solve();
  return 0;
}
