#include <bits/stdc++.h>
using namespace std;
const int N = 200009;
queue<int> q;
int n, m, k, head[N], x[N], y[N], vis[N], bin[N], cn, f[N][30], dep[N], Ans[N];
vector<int> b[N];
map<pair<int, int>, int> S;
struct Edge {
  int nxt, to;
} g[N * 2];
void add(int from, int to) {
  g[++cn].nxt = head[from];
  g[cn].to = to;
  head[from] = cn;
}
void init() {
  scanf("%d %d %d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    scanf("%d %d", &x[i], &y[i]);
    add(x[i], y[i]), add(y[i], x[i]);
  }
}
void dfs(int x) {
  vis[x] = 1;
  for (int i = head[x]; i; i = g[i].nxt) {
    int v = g[i].to;
    if (!vis[v]) {
      b[x].push_back(v);
      b[v].push_back(x);
      S[make_pair(x, v)] = 1;
      dfs(v);
    }
  }
}
void DFS(int x, int fa) {
  for (int i = 0; i < b[x].size(); i++) {
    int v = b[x][i];
    if (v == fa) continue;
    f[v][0] = x;
    dep[v] = dep[x] + 1;
    DFS(v, x);
  }
}
void get(int &x, int k) {
  for (int i = 20; i >= 0; i--)
    if (k >= 1 << i) k -= 1 << i, x = f[x][i];
}
int LCA(int x, int y) {
  if (dep[x] != dep[y]) {
    if (dep[x] < dep[y]) swap(x, y);
    get(x, dep[x] - dep[y]);
  }
  if (x == y) return x;
  for (int i = 20; i >= 1; i--)
    if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
  return f[x][0];
}
struct fuck {
  int a, b, c;
  bool operator<(const fuck &A) const { return c < A.c; }
} A[N];
int B[N];
int del[N], deg[N];
void work() {
  dfs(1);
  DFS(1, -1);
  for (int j = 1; j <= 20; j++)
    for (int i = 1; i <= n; i++) f[i][j] = f[f[i][j - 1]][j - 1];
  int cnt = 0;
  for (int i = 1; i <= m; i++)
    if (S[make_pair(x[i], y[i])] == 0 && S[make_pair(y[i], x[i])] == 0)
      A[++cnt] =
          (fuck){x[i], y[i], dep[x[i]] + dep[y[i]] - 2 * dep[LCA(x[i], y[i])]};
  sort(A + 1, A + 1 + cnt);
  for (int i = 1; i <= cnt; i++) {
    if (A[i].c + 1 <= k) {
      puts("2");
      printf("%d\n", A[i].c + 1);
      int L = LCA(A[i].a, A[i].b);
      for (int j = A[i].a; j != L; j = f[j][0]) printf("%d ", j);
      int Cnt = 0;
      for (int j = A[i].b; j != L; j = f[j][0]) B[++Cnt] = j;
      printf("%d ", L);
      for (int j = Cnt; j >= 1; j--) printf("%d ", B[j]);
      puts("");
      return;
    } else {
      puts("1");
      int now = k + 1 >> 1;
      int L = LCA(A[i].a, A[i].b);
      if (dep[A[i].a] < dep[A[i].b]) swap(A[i].a, A[i].b);
      for (int j = A[i].a; dep[j] >= dep[L] && now; j = f[j][1], now--)
        printf("%d ", j);
      for (int j = f[A[i].b][0]; dep[j] > dep[L] && now; j = f[j][1], now--)
        printf("%d ", j);
      puts("");
      return;
    }
  }
  puts("1");
  for (int i = 1; i <= m; i++) deg[x[i]]++, deg[y[i]]++;
  for (int i = 1; i <= n; i++)
    if (deg[i] == 1) q.push(i);
  int ans = 0;
  while (!q.empty()) {
    if (ans == k + 1 >> 1) break;
    int x = q.front();
    q.pop();
    if (!del[x]) Ans[++ans] = x;
    for (int i = head[x]; i; i = g[i].nxt) {
      int v = g[i].to;
      if (!del[x]) del[v] = 1;
      if (deg[v] == 1) continue;
      deg[v]--;
      if (deg[v] == 1) q.push(v);
    }
  }
  for (int i = 1; i <= ans; i++) printf("%d ", Ans[i]);
  puts("");
}
int main() {
  init();
  work();
  return 0;
}
