#include <bits/stdc++.h>
using namespace std;
const long double pi = 3.14159265358979323846264338;
const long long mod = 1000000007;
long long int pow(long long int x, unsigned long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long int invmod(long long int a, long long int m) { return pow(a, m - 2); }
const long long int maxn = 2e5 + 5;
vector<long long int> adj[maxn], pos(maxn, -1), s;
vector<long long int> cycle;
vector<long long int> c1, c2;
bool a = false;
void dfs1(long long int st, long long int p, bool t) {
  if (t)
    c1.push_back(st);
  else
    c2.push_back(st);
  for (long long int x : adj[st]) {
    if (x == p) continue;
    dfs1(x, st, 1 - t);
  }
}
void cdfs(long long int st) {
  pos[st] = s.size();
  s.push_back(st);
  if (!a) {
    long long int l = -1;
    for (long long int x : adj[st]) {
      if (pos[x] != -1 && pos[st] - pos[x] > 1) l = max(l, pos[x]);
    }
    if (l != -1) {
      for (long long int i = l; i <= pos[st]; i++) {
        cycle.push_back(s[i]);
      }
      a = true;
      return;
    }
  }
  for (long long int x : adj[st]) {
    if (pos[x] == -1) cdfs(x);
  }
  s.pop_back();
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int n, m, k;
  cin >> n >> m >> k;
  for (long long int i = 0; i < m; i++) {
    long long int x, y;
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  if (m == n - 1) {
    dfs1(1, 0, 0);
    long long int tt;
    if (k % 2)
      tt = k / 2 + 1;
    else
      tt = k / 2;
    if (c1.size() > c2.size()) c2 = c1;
    cout << 1 << endl;
    for (long long int i = 0; i < tt; i++) {
      cout << c2[i] << " ";
    }
    cout << endl;
    exit(0);
  }
  cdfs(1);
  if (cycle.size() <= k) {
    cout << 2 << endl;
    cout << cycle.size() << endl;
    for (long long int i : cycle) {
      cout << i << " ";
    }
    cout << endl;
  } else {
    cout << 1 << endl;
    for (long long int i = 0; i < (k + 1) / 2; i++) {
      cout << cycle[2 * i] << " ";
    }
    cout << endl;
  }
}
