Problem: The evil Bumbershoot corporation produces clones for gruesome experiments in a vast underground lab. On one occasion, the corp cloned a boy Andryusha who was smarter than his comrades. Immediately Andryusha understood that something fishy was going on there. He rallied fellow clones to go on a feud against the evil corp, and they set out to find an exit from the lab. The corp had to reduce to destroy the lab complex.

The lab can be pictured as a connected graph with n vertices and m edges. k clones of Andryusha start looking for an exit in some of the vertices. Each clone can traverse any edge once per second. Any number of clones are allowed to be at any vertex simultaneously. Each clone is allowed to stop looking at any time moment, but he must look at his starting vertex at least. The exit can be located at any vertex of the lab, hence each vertex must be visited by at least one clone.

Each clone can visit at most <image> vertices before the lab explodes.

Your task is to choose starting vertices and searching routes for the clones. Each route can have at most <image> vertices.

Input

The first line contains three integers n, m, and k (1 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105, 1 ≤ k ≤ n) — the number of vertices and edges in the lab, and the number of clones.

Each of the next m lines contains two integers xi and yi (1 ≤ xi, yi ≤ n) — indices of vertices connected by the respective edge. The graph is allowed to have self-loops and multiple edges.

The graph is guaranteed to be connected.

Output

You should print k lines. i-th of these lines must start with an integer ci (<image>) — the number of vertices visited by i-th clone, followed by ci integers — indices of vertices visited by this clone in the order of visiting. You have to print each vertex every time it is visited, regardless if it was visited earlier or not.

It is guaranteed that a valid answer exists.

Examples

Input

3 2 1
2 1
3 1


Output

3 2 1 3


Input

5 4 2
1 2
1 3
1 4
1 5


Output

3 2 1 3
3 4 1 5

Note

In the first sample case there is only one clone who may visit vertices in order (2, 1, 3), which fits the constraint of 6 vertices per clone.

In the second sample case the two clones can visited vertices in order (2, 1, 3) and (4, 1, 5), which fits the constraint of 5 vertices per clone.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
class Graph {
 public:
  Graph(int vert_count, int pair_count);
  Graph(int vert_count, int pair_count, int root);
  ~Graph();
  void init();
  void addPair(int first_vert, int second_vert);
  bool nextVert();
  int getVertCnt();
  int getPairsCnt();
  bool isUnvisited();
  int getCurrentVertex();
  ostream &write(stringstream &os);

 private:
  struct Vertex {
    int edge_ptr;
    int cur_edge;
    bool visited;
    int prev_vert;
  };
  struct Edge {
    int pair;
    int next;
  };
  struct Pair {
    int first_vert;
    int second_vert;
    bool broken;
  };
  Vertex *vertex;
  Edge *edges;
  Pair *pairs;
  int vert_count;
  int pair_count;
  int edge_count;
  int pt_edges, pt_pairs;
  int current_vert;
  int root;
  void addEdge(int vert, int pairs_ind);
  bool nextEdge(int vert);
};
Graph::Graph(int vert_count_p, int pair_count_p)
    : Graph(vert_count_p, pair_count_p, 1) {}
Graph::Graph(int vert_count_p, int pair_count_p, int root_p) {
  pt_pairs = 0;
  root = root_p;
  current_vert = 0;
  edge_count = 2 * pair_count_p;
  vert_count = vert_count_p + 1;
  pair_count = pair_count_p;
}
void Graph::init() {
  vertex = (Vertex *)::operator new(sizeof(Vertex) * vert_count);
  for (int k = 0; k < vert_count; ++k) {
    (vertex + k)->edge_ptr = -1;
    (vertex + k)->cur_edge = -1;
    (vertex + k)->visited = false;
    (vertex + k)->prev_vert = -1;
  }
  pairs = (Pair *)::operator new(sizeof(Pair) * pair_count);
  edges = (Edge *)::operator new(sizeof(Edge) * edge_count);
  for (pt_edges = 0; pt_edges < edge_count; pt_edges++)
    (edges + pt_edges)->next = pt_edges - 1;
  pt_edges--;
}
void Graph::addPair(int first_vert_p, int second_vert_p) {
  Pair *cur_pair = pairs + pt_pairs;
  cur_pair->first_vert = first_vert_p;
  cur_pair->second_vert = second_vert_p;
  cur_pair->broken = false;
  addEdge(cur_pair->first_vert, pt_pairs);
  if (cur_pair->first_vert != cur_pair->second_vert)
    addEdge(cur_pair->second_vert, pt_pairs);
  pt_pairs++;
}
Graph::~Graph() {
  delete (char *)vertex;
  delete (char *)edges;
  delete (char *)pairs;
}
void Graph::addEdge(int vert, int pairs_ind) {
  int tmp = (edges + pt_edges)->next;
  (edges + pt_edges)->pair = pairs_ind;
  (edges + pt_edges)->next = (vertex + vert)->edge_ptr;
  (vertex + vert)->edge_ptr = pt_edges;
  (vertex + vert)->cur_edge = pt_edges;
  pt_edges = tmp;
}
bool Graph::nextVert() {
  if (current_vert == root && (vertex + current_vert)->cur_edge == -1) {
    return false;
  } else {
    if (current_vert == 0)
      current_vert = root;
    else {
      int prev_vert, next_pair, next_vert;
      (vertex + current_vert)->visited = true;
      int edge_exists = nextEdge(current_vert);
      if (!edge_exists) {
        prev_vert = (vertex + current_vert)->prev_vert;
        current_vert = prev_vert;
      } else {
        next_pair = (edges + (vertex + current_vert)->cur_edge)->pair;
        next_vert = (((pairs + next_pair)->first_vert) == current_vert)
                        ? ((pairs + next_pair)->second_vert)
                        : ((pairs + next_pair)->first_vert);
        (vertex + next_vert)->prev_vert = current_vert;
        (vertex + current_vert)->cur_edge =
            (edges + ((vertex + current_vert)->cur_edge))->next;
        current_vert = next_vert;
      }
    }
    return true;
  }
}
bool Graph::nextEdge(int vert) {
  int cur_pair, next_vert;
  bool flag = true;
  int ptr;
  ptr = (vertex + vert)->cur_edge;
  while (ptr >= 0 && flag) {
    cur_pair = (edges + ptr)->pair;
    if (((pairs + cur_pair)->first_vert) == ((pairs + cur_pair)->second_vert)) {
      ptr = (edges + ptr)->next;
      continue;
    } else if (((pairs + cur_pair)->first_vert) == vert) {
      next_vert = (pairs + cur_pair)->second_vert;
      if ((vertex + next_vert)->visited) {
        ptr = (edges + ptr)->next;
        continue;
      }
    } else {
      next_vert = (pairs + cur_pair)->first_vert;
      if ((vertex + next_vert)->visited) {
        ptr = (edges + ptr)->next;
        continue;
      }
    }
    (vertex + vert)->cur_edge = ptr;
    flag = false;
  }
  if (ptr < 0)
    return false;
  else
    return true;
}
ostream &Graph::write(stringstream &os) {
  int cur_edge, cur_pair;
  bool cmp;
  os << vert_count - 1 << " " << pair_count << endl;
  for (int cur_vert = 1; cur_vert < vert_count; cur_vert++) {
    cur_edge = (vertex + cur_vert)->edge_ptr;
    while (cur_edge >= 0) {
      cur_pair = (edges + cur_edge)->pair;
      cmp = (pairs + cur_pair)->first_vert == cur_vert;
      os << ((cmp) ? ((pairs + cur_pair)->first_vert)
                   : ((pairs + cur_pair)->second_vert));
      os << ":"
         << ((cmp) ? ((pairs + cur_pair)->second_vert)
                   : ((pairs + cur_pair)->first_vert))
         << endl;
      cur_edge = (edges + cur_edge)->next;
    }
  }
  return os;
}
int Graph::getVertCnt() { return vert_count - 1; }
int Graph::getPairsCnt() { return pair_count; }
bool Graph::isUnvisited() { return !((vertex + current_vert)->visited); }
int Graph::getCurrentVertex() { return current_vert; }
using namespace std;
class Underground : public Graph {
 public:
  Underground(int vert_count, int pairs_count, int clone_count)
      : Graph(vert_count, pairs_count, 1), clone_count(clone_count) {}
  Underground(int vert_count, int pairs_count, int clone_count, int root)
      : Graph(vert_count, pairs_count, root), clone_count(clone_count) {}
  void getData();
  void getResult(stringstream &ss);
  void printResult(stringstream &ss);

 private:
  int clone_count;
};
void Underground::getResult(stringstream &ss) {
  int vert_cnt = getVertCnt();
  int steps_cnt = vert_cnt * 2;
  int pairs_cnt = getPairsCnt();
  stringstream ss_temp;
  int max_steps_cnt = (int)ceil((double)vert_cnt * 2 / clone_count);
  for (int clone = 0; clone < clone_count; ++clone) {
    if (vert_cnt > 0) {
      int ind;
      int rsteps = (steps_cnt >= max_steps_cnt) ? max_steps_cnt : steps_cnt;
      for (ind = 0; ind < rsteps; ++ind) {
        nextVert();
        ss_temp << " " << getCurrentVertex();
        if (isUnvisited()) vert_cnt--;
        steps_cnt--;
        if (vert_cnt == 0) {
          ss << ind + 1 << ss_temp.str() << endl;
          ss_temp.str("");
          break;
        }
      }
      if (ind == rsteps) {
        ss << rsteps << ss_temp.str() << endl;
        ss_temp.str("");
      }
    } else {
      ss << 1 << " " << getCurrentVertex() << endl;
    }
  }
}
void Underground::getData() {
  init();
  int first_vert, second_vert;
  for (int line = 0; line < getPairsCnt(); ++line) {
    cin >> first_vert >> second_vert;
    addPair(first_vert, second_vert);
  }
}
void Underground::printResult(stringstream &ss) { cout << ss.str(); }
int main() {
  cin.sync_with_stdio(false);
  Underground *ug;
  int vert_count, pairs_count, clone_count;
  cin >> vert_count >> pairs_count >> clone_count;
  ug = new Underground(vert_count, pairs_count, clone_count);
  ug->getData();
  stringstream ss;
  ug->getResult(ss);
  ug->printResult(ss);
}