#include <bits/stdc++.h>
std::vector<int> cut_cycle(const std::vector<int>& prev_node, const int start) {
  std::vector<int> result{start};
  int node = prev_node[start];
  while (node != start) {
    result.push_back(node);
    node = prev_node[node];
  }
  return result;
}
void show_cycle(const std::vector<int>& cycle) {
  std::cout << 2 << '\n' << cycle.size() << '\n';
  for (auto i = 0; i < cycle.size(); ++i) {
    if (i > 0) std::cout << ' ';
    std::cout << cycle[i] + 1;
  }
}
void show_set(const std::vector<int>& set) {
  std::cout << "1\n";
  for (auto i = 0; i < set.size(); ++i) {
    if (i > 0) std::cout << ' ';
    std::cout << set[i] + 1;
  }
}
void solve(const std::vector<std::vector<int>>& nodes,
           const std::vector<int>& cycle, const int k) {
  if (cycle.size() <= k) {
    return show_cycle(cycle);
  }
  std::unordered_map<int, int> map;
  for (auto i = 1; i < cycle.size(); i += 2) {
    map[cycle[i]] = i;
  }
  int from{-1}, to{-1};
  for (auto i = 1; i < cycle.size() && from == -1; i += 2) {
    for (const auto neighbor : nodes[cycle[i]]) {
      const auto c = map.find(neighbor);
      if (c != map.end()) {
        from = i;
        to = c->second;
        break;
      }
    }
  }
  if (from == -1) {
    std::vector<int> independent_set((k + 1) >> 1);
    for (auto i = 0; i < independent_set.size(); ++i) {
      independent_set[i] = cycle[(i << 1) + 1];
    }
    return show_set(independent_set);
  }
  const auto len = (cycle.size() + 1) >> 1;
  std::vector<int> next_cycle;
  if ((to - from + 1) > len) {
    for (auto i = to; i < cycle.size(); i += 2) next_cycle.push_back(cycle[i]);
    for (auto i = 1; i <= from; i += 2) next_cycle.push_back(cycle[i]);
  } else {
    for (auto i = from; i <= to; i += 2) next_cycle.push_back(cycle[i]);
  }
  solve(nodes, next_cycle, k);
}
void no_loop(const std::vector<std::vector<int>>& nodes, const int k) {
  std::vector<int> depth(nodes.size(), -1);
  depth[0] = 0;
  std::stack<int> stack;
  stack.push(0);
  while (!stack.empty()) {
    const auto top = stack.top();
    stack.pop();
    for (const auto next : nodes[top])
      if (depth[next] == -1) {
        depth[next] = 1 - depth[top];
        stack.push(next);
      }
  }
  const auto even = std::count(depth.begin(), depth.end(), 0);
  std::vector<int> set;
  if (even >= (k + 1) >> 1) {
    for (auto i = 0; i < depth.size(); ++i) {
      if (depth[i] == 0) set.push_back(i);
      if (set.size() == (k + 1) >> 1) break;
    }
  } else {
    for (auto i = 0; i < depth.size(); ++i) {
      if (depth[i] == 1) set.push_back(i);
      if (set.size() == (k + 1) >> 1) break;
    }
  }
  show_set(set);
}
int main() {
  std::cin.tie(nullptr);
  std::cin.sync_with_stdio(false);
  int n, m, k;
  std::cin >> n >> m >> k;
  std::vector<std::vector<int>> nodes(n);
  for (auto i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    --u;
    --v;
    nodes[u].push_back(v);
    nodes[v].push_back(u);
  }
  std::vector<int> prev_node(n, -1);
  std::vector<bool> popped(n, false);
  std::stack<int> stack;
  stack.push(0);
  int loop_start{-1};
  while (!stack.empty() && loop_start == -1) {
    const auto top = stack.top();
    stack.pop();
    popped[top] = true;
    for (const auto next : nodes[top])
      if (next != prev_node[top]) {
        if (popped[next]) {
          loop_start = top;
          prev_node[next] = top;
          break;
        } else {
          prev_node[next] = top;
          stack.push(next);
        }
      }
  }
  if (loop_start == -1) {
    no_loop(nodes, k);
  } else {
    solve(nodes, cut_cycle(prev_node, loop_start), k);
  }
}
