#include <bits/stdc++.h>
using namespace std;
int A[110000];
vector<int> V[110000], s, C, O[5];
bool dfs(int k) {
  A[k] = s.size();
  O[s.size() % 2].push_back(k);
  s.push_back(k);
  int pos = -1;
  for (int i = 0; i < V[k].size(); i++) {
    if (A[V[k][i]] != -1 && A[k] - A[V[k][i]] > 1) pos = max(pos, A[V[k][i]]);
  }
  if (pos != -1) {
    for (int i = pos; i <= A[k]; i++) C.push_back(s[i]);
    return 1;
  }
  for (int i = 0; i < V[k].size(); i++)
    if (A[V[k][i]] == -1)
      if (dfs(V[k][i])) {
        return 1;
      }
  s.pop_back();
  return 0;
}
int main() {
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    V[a].push_back(b);
    V[b].push_back(a);
  }
  memset(A, -1, sizeof(A));
  if (dfs(1)) {
    if (C.size() <= k) {
      printf("2\n%d\n", C.size());
      for (int i = 0; i < C.size(); i++) printf("%d ", C[i]);
    } else {
      printf("1\n");
      for (int i = 0; i < (k + 1) / 2; i++) printf("%d ", C[i * 2]);
    }
  } else {
    if (O[0].size() < O[1].size()) swap(O[1], O[0]);
    printf("1\n");
    for (int i = 0; i < (k + 1) / 2; i++) printf("%d ", O[0][i]);
  }
}
