#include <bits/stdc++.h>
using namespace std;
void __print(int first) { cerr << first; }
void __print(long first) { cerr << first; }
void __print(long long first) { cerr << first; }
void __print(unsigned first) { cerr << first; }
void __print(unsigned long first) { cerr << first; }
void __print(unsigned long long first) { cerr << first; }
void __print(float first) { cerr << first; }
void __print(double first) { cerr << first; }
void __print(long double first) { cerr << first; }
void __print(char first) { cerr << '\'' << first << '\''; }
void __print(const char *first) { cerr << '\"' << first << '\"'; }
void __print(const string &first) { cerr << '\"' << first << '\"'; }
void __print(bool first) { cerr << (first ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &first) {
  cerr << '{';
  __print(first.first);
  cerr << ',';
  __print(first.second);
  cerr << '}';
}
template <typename T>
void __print(const T &first) {
  int f = 0;
  cerr << '{';
  for (auto &i : first) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
vector<set<long long> > vect(200000);
vector<long long> color(200000, -1), odd_cycle;
long long found = 0;
void dfs(long long node, long long parent) {
  if (color[node] != -1) {
    if (color[node] == color[parent]) {
      odd_cycle.push_back(node);
      found = 1;
      return;
    }
    return;
  }
  color[node] = (color[parent] + 1) % 2;
  for (auto &child : vect[node]) {
    dfs(child, node);
    if (found) {
      if (odd_cycle.back() != odd_cycle[0] || odd_cycle.size() < 2)
        odd_cycle.push_back(node);
      return;
    }
  }
}
void solve1(long long n, long long k) {
  vector<long long> black, white;
  for (long long i = 1; i < n + 1; i++) {
    if (color[i] == 0)
      black.push_back(i);
    else
      white.push_back(i);
  }
  if (white.size() < black.size()) white = black;
  cout << "1"
       << "\n";
  for (long long i = 0; i < k; i++) cout << white[i] << " ";
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long n, m, k;
  cin >> n >> m >> k;
  long long u, v;
  for (long long i = 0; i < m; i++) {
    cin >> u >> v;
    vect[u].insert(v);
    vect[v].insert(u);
  }
  color[0] = 0, dfs(1, 0);
  if (!found) {
    solve1(n, (k + 1) / 2);
    return 0;
  }
  odd_cycle.pop_back();
  reverse(odd_cycle.begin(), odd_cycle.end());
  ;
  if (odd_cycle.size() <= k) {
    cout << "2"
         << "\n";
    cout << odd_cycle.size() << "\n";
    for (auto &node : odd_cycle) cout << node << " ";
    return 0;
  }
  set<long long> white;
  long long cnt = 0;
  for (int i = 0; i < odd_cycle.size(); i += 2) {
    white.insert(odd_cycle[i]);
    cnt++;
    if (cnt == (k + 1) / 2) break;
  }
  long long l = -1, r = -1;
  for (auto &node : white) {
    for (auto &vertice : vect[node]) {
      if (white.find(vertice) != white.end()) {
        l = node, r = vertice;
        break;
      }
    }
    if (l != -1) break;
  }
  if (l == -1) {
    cout << "1"
         << "\n";
    for (auto &node : white) cout << node << " ";
    return 0;
  }
  for (long long i = 0; i < odd_cycle.size(); i++) {
    if (l == odd_cycle[i]) {
      l = i;
      break;
    }
  }
  for (long long i = 0; i < odd_cycle.size(); i++) {
    if (r == odd_cycle[i]) {
      r = i;
      break;
    }
  }
  long long L = min(l, r), R = max(l, r);
  assert(R - L + 1 <= k);
  for (long long i = L; i < R + 1; i++) cout << odd_cycle[i] << " ";
  return 0;
}
