#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e5 + 5, MOD = 1e9 + 7;
template <typename T>
inline void read(T& x, T f = 1, char ch = getchar()) {
  x = 0;
  while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
  x *= f;
}
int tc, n, m, k, color[MAXN], vis2[MAXN], cnt[2], maintain[MAXN];
vector<int> G[MAXN], ans2, son[MAXN], other[MAXN];
inline void dfs4(int cur, int col) {
  vis2[cur] = 1;
  color[cur] = col, cnt[col - 1]++;
  for (auto& to : G[cur])
    if (!vis2[to]) dfs4(to, 3 - col);
}
inline bool solve1() {
  cout << 1 << "\n";
  int tmp = (k & 1) ? k / 2 + 1 : k / 2;
  dfs4(1, 1);
  int tot = 0;
  for (int i = 1; i <= n; i++)
    if (color[i] == 1) {
      bool judge = true;
      for (auto& to : G[i])
        if (color[i] == color[to]) {
          judge = false;
          maintain[to] = true;
        }
      if (!judge && !maintain[i]) continue;
      tot++;
      ans2.push_back(i);
      if (tot == tmp) {
        for (auto& j : ans2) cout << j << " ";
        return true;
      }
    }
  tot = 0;
  memset(maintain, 0, sizeof(maintain));
  for (int i = 1; i <= n; i++)
    if (color[i] == 2) {
      bool judge = true;
      for (auto& to : G[i])
        if (color[i] == color[to]) {
          judge = false;
          maintain[to] = true;
        }
      if (!judge && !maintain[i]) continue;
      tot++, cout << i << " ";
      if (tot == tmp) return true;
    }
  return false;
}
array<int, MAXN> fa, depth, top, rnk, sz, hSon, in, vis;
inline void dfs1(int cur, int f) {
  vis[cur] = 1;
  sz[cur] = 1, depth[cur] = depth[f] + 1, fa[cur] = f;
  for (int i = 0; i < G[cur].size(); i++) {
    int to = G[cur][i];
    if (to == f || vis[to]) {
      if (vis[to]) other[cur].push_back(to);
      continue;
    }
    dfs1(to, cur);
    son[cur].push_back(to);
    sz[cur] += sz[to];
    if (!hSon[cur] || sz[to] > sz[hSon[cur]]) hSon[cur] = to;
  }
}
inline void dfs2(int cur, int f) {
  static int tim;
  in[cur] = ++tim, top[cur] = f, rnk[tim] = cur;
  if (!hSon[cur]) return;
  dfs2(hSon[cur], f);
  for (int i = 0; i < son[cur].size(); i++) {
    int to = son[cur][i];
    if (to == hSon[cur] || to == fa[cur]) continue;
    dfs2(to, to);
  }
}
inline int LCA(int u, int v) {
  while (top[u] != top[v]) {
    if (depth[top[u]] < depth[top[v]]) swap(u, v);
    u = fa[top[u]];
  }
  return in[u] < in[v] ? u : v;
}
inline void dfs3(int cur, int lca) {
  if (cur == lca) return;
  dfs3(fa[cur], lca);
  ans2.push_back(cur);
}
inline bool solve2(int st) {
  dfs1(1, 0), dfs2(1, 1);
  for (int cur = 1; cur <= n; cur++) {
    for (auto& to : other[cur]) {
      int lca = LCA(cur, to);
      int len = depth[cur] - depth[lca];
      len += depth[to] - depth[lca] + 1;
      if (3 <= len && len <= k) {
        int tmp = cur;
        while (tmp != lca) {
          ans2.push_back(tmp);
          tmp = fa[tmp];
        }
        ans2.push_back(lca);
        dfs3(to, lca);
        cout << 2 << "\n";
        cout << ans2.size() << "\n";
        for (auto& j : ans2) cout << j << " ";
        return true;
      }
    }
  }
  return false;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m >> k;
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    G[u].push_back(v), G[v].push_back(u);
  }
  if (!solve2(1)) solve1();
  return 0;
}
