#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct Edge {
  int u, v;
  int next;
} edge[maxn * 2];
int tol;
int head[maxn];
void addEdge(int u, int v) {
  edge[tol].v = v;
  edge[tol].next = head[u];
  head[u] = tol++;
}
int vis[maxn / 2];
int node[maxn / 2];
int in1, in2;
int ans1[maxn / 2];
int ans2[maxn / 2];
void bfs(int x) {
  queue<int> que;
  que.push(x);
  vis[x] = 1;
  ans1[++in1] = x;
  node[x] = 1;
  while (!que.empty()) {
    int s = que.front();
    que.pop();
    for (int i = head[s]; i != 0; i = edge[i].next) {
      int v = edge[i].v;
      if (vis[v] == 1) continue;
      if (node[s] == 1) {
        ans2[++in2] = v;
        node[v] = 2;
        vis[v] = 1;
      } else {
        ans1[++in1] = v;
        node[v] = 1;
        vis[v] = 1;
      }
      que.push(v);
    }
  }
}
int cnt[maxn / 2];
int vis1[maxn / 2];
int pre1[maxn / 2];
int ans3[maxn / 2];
int in;
int mn;
int end1, sta;
void dfs(int s, int pre) {
  cnt[s] = cnt[pre] + 1;
  pre1[s] = pre;
  vis1[s] = 1;
  for (int i = head[s]; i != 0; i = edge[i].next) {
    int v = edge[i].v;
    if (v == pre) continue;
    if (vis1[v] == 1) {
      int ele = cnt[s] - cnt[v] + 1;
      if (ele >= 0 && mn > ele) {
        mn = ele;
        end1 = s;
        sta = v;
      }
      continue;
    }
    dfs(v, s);
  }
}
int main() {
  int n, len1, k;
  scanf("%d%d%d", &n, &len1, &k);
  tol = 1;
  in1 = in2 = 0;
  mn = 1e9;
  for (int i = 1; i <= len1; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs(1, 0);
  if (mn != 1e9) {
    for (int i = end1; i != sta; i = pre1[i]) {
      ans3[++in] = i;
    }
    ans3[++in] = sta;
    if (mn <= k) {
      printf("2\n");
      printf("%d\n", mn);
      for (int i = 1; i <= in; i++) {
        printf("%d ", ans3[i]);
      }
      printf("\n");
    } else {
      printf("1\n");
      int ele = (k + 1) / 2;
      int c = 0;
      int i = 1;
      while (c < ele && i <= in) {
        printf("%d ", ans3[i]);
        i += 2;
        c++;
      }
      printf("\n");
    }
  } else {
    bfs(1);
    printf("1\n");
    if (in1 >= in2) {
      for (int i = 1; i <= (k + 1) / 2; i++) {
        printf("%d ", ans1[i]);
      }
    } else {
      for (int i = 1; i <= (k + 1) / 2; i++) {
        printf("%d ", ans2[i]);
      }
    }
    printf("\n");
  }
}
