Problem: You are given a bipartite graph G = (U, V, E), U is the set of vertices of the first part, V is the set of vertices of the second part and E is the set of edges. There might be multiple edges.

Let's call some subset of its edges <image> k-covering iff the graph <image> has each of its vertices incident to at least k edges. Minimal k-covering is such a k-covering that the size of the subset <image> is minimal possible.

Your task is to find minimal k-covering for each <image>, where minDegree is the minimal degree of any vertex in graph G.

Input

The first line contains three integers n1, n2 and m (1 ≤ n1, n2 ≤ 2000, 0 ≤ m ≤ 2000) — the number of vertices in the first part, the number of vertices in the second part and the number of edges, respectively.

The i-th of the next m lines contain two integers ui and vi (1 ≤ ui ≤ n1, 1 ≤ vi ≤ n2) — the description of the i-th edge, ui is the index of the vertex in the first part and vi is the index of the vertex in the second part.

Output

For each <image> print the subset of edges (minimal k-covering) in separate line.

The first integer cntk of the k-th line is the number of edges in minimal k-covering of the graph. Then cntk integers follow — original indices of the edges which belong to the minimal k-covering, these indices should be pairwise distinct. Edges are numbered 1 through m in order they are given in the input.

Examples

Input

3 3 7
1 2
2 3
1 3
3 2
3 3
2 1
2 1


Output

0 
3 3 7 4 
6 1 3 6 7 4 5 


Input

1 1 5
1 1
1 1
1 1
1 1
1 1


Output

0 
1 5 
2 4 5 
3 3 4 5 
4 2 3 4 5 
5 1 2 3 4 5 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxm = 1e5 + 10;
const int inf = 0x3f3f3f3f;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &x) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (x = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= f;
  return 1;
}
inline bool read(char &x) {
  while ((x = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                           (iS == iT ? EOF : *iS++))
                        : *iS++)) == ' ' ||
         x == '\n' || x == '\r')
    ;
  return x != EOF;
}
inline bool read(char *x) {
  while ((*x = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                            (iS == iT ? EOF : *iS++))
                         : *iS++)) == '\n' ||
         *x == ' ' || *x == '\r')
    ;
  if (*x == EOF) return 0;
  while (!(*x == '\n' || *x == ' ' || *x == '\r' || *x == EOF))
    *(++x) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                          (iS == iT ? EOF : *iS++))
                       : *iS++);
  *x = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &x, B &...y) {
  return read(x) && read(y...);
}
template <typename A>
inline bool write(A x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) qu[++qr] = x % 10 + '0', x /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char x) {
  putc(x);
  return 0;
}
inline bool write(const char *x) {
  while (*x) {
    putc(*x);
    ++x;
  }
  return 0;
}
inline bool write(char *x) {
  while (*x) {
    putc(*x);
    ++x;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A x, B... y) {
  return write(x) || write(y...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
vector<int> ed[maxm];
set<int> fsafasfas;
vector<int> ans[maxm];
int deg1[maxm], deg2[maxm];
int s, t, head[maxm], cnt, dep[maxm], now[maxm], zz[maxm];
struct Edge {
  int v, w, nxt, id;
} e[maxm * 2];
void addedge(int u, int v, int w, int id) {
  e[cnt] = {v, w, head[u], id};
  head[u] = cnt++;
  e[cnt] = {u, 0, head[v], id};
  head[v] = cnt++;
}
int bfs() {
  queue<int> q;
  while (!q.empty()) q.pop();
  for (int i = s; i <= t; i++) {
    dep[i] = -1;
    now[i] = -1;
  }
  dep[s] = 0;
  q.push(s);
  now[s] = head[s];
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i != -1; i = e[i].nxt) {
      int v = e[i].v;
      if (e[i].w > 0 && dep[v] == -1) {
        dep[v] = dep[u] + 1;
        now[v] = head[v];
        q.push(v);
      }
    }
  }
  return dep[t] != -1;
}
int dfs(int u, int mi) {
  if (mi == 0 || u == t) return mi;
  int tmp, sum = 0;
  for (int i = now[u]; i != -1 && mi; i = e[i].nxt) {
    now[u] = i;
    int v = e[i].v;
    if (e[i].w > 0 && dep[v] == dep[u] + 1) {
      tmp = dfs(v, min(mi, e[i].w));
      e[i].w -= tmp;
      e[i ^ 1].w += tmp;
      sum += tmp;
      mi -= tmp;
      if (!mi) break;
    }
  }
  return sum;
}
int dinic() {
  int ans = 0;
  while (bfs()) {
    ans += dfs(s, inf);
  }
  return ans;
}
int main() {
  memset(head, -1, sizeof(head));
  int n1, n2, m;
  read(n1, n2, m);
  s = 0, t = n1 + n2 + 1;
  for (int i = 1; i <= m; i++) {
    int u, v;
    read(u, v);
    ed[u].push_back(v);
    addedge(u, n1 + v, 1, i);
    deg1[u]++;
    deg2[v]++;
    fsafasfas.insert(cnt - 2);
  }
  int mindeg = inf;
  for (int i = 1; i <= n1; i++) mindeg = min(mindeg, deg1[i]);
  for (int i = 1; i <= n2; i++) mindeg = min(mindeg, deg2[i]);
  for (int i = 1; i <= n1; i++) addedge(s, i, deg1[i] - mindeg, 0);
  for (int i = 1; i <= n2; i++) addedge(n1 + i, t, deg2[i] - mindeg, 0);
  int res = 0;
  fsafasfas.insert(inf);
  for (int i = mindeg; i >= 1; i--) {
    res += dinic();
    zz[i] = m - res;
    set<int>::iterator it = fsafasfas.begin();
    set<int>::iterator it1 = it;
    while (1) {
      if ((*it) >= mod) break;
      it1 = it;
      it++;
      if (e[*it1].w > 0) ans[i].push_back(e[*it1].id);
    }
    for (int j = 1; j <= n1; j++) addedge(s, j, 1, 0);
    for (int j = 1; j <= n2; j++) addedge(n1 + j, t, 1, 0);
  }
  for (int i = 0; i <= mindeg; i++) {
    printf("%d", zz[i]);
    for (int j : ans[i]) printf(" %d", j);
    printf("\n");
  }
  return 0;
}