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 NR = 5005;
const int MR = 1e5 + 10;
const int INF = 0x3f3f3f3f;
void Min(int& x, int y) { x = min(x, y); }
void Max(int& x, int y) { x = max(x, y); }
int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return x * f;
}
int n1, n2, m, S, T, mn = 0x3f3f3f3f;
int rd[NR];
int u[NR], v[NR];
int to[MR], nxt[MR], val[MR], head[NR], tot = 1;
void add(int x, int y, int z) {
  to[tot] = y, val[tot] = z, nxt[tot] = head[x], head[x] = tot++;
}
int dep[NR], now[NR];
bool bfs() {
  memset(dep, 0, sizeof(dep));
  dep[S] = 1;
  queue<int> q;
  q.push(S);
  now[S] = head[S];
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i; i = nxt[i]) {
      int y = to[i];
      if (val[i] && !dep[y]) {
        dep[y] = dep[x] + 1;
        q.push(y);
        now[y] = head[y];
        if (y == T) return 1;
      }
    }
  }
  return 0;
}
int dinic(int x, int flow) {
  if (x == T) return flow;
  int mxflow = 0;
  for (int i = now[x]; i; i = nxt[i]) {
    int y = to[i];
    now[x] = i;
    if (mxflow == flow) return flow;
    if (val[i] && dep[y] == dep[x] + 1) {
      int num = dinic(y, min(val[i], flow - mxflow));
      val[i] -= num, val[i * 2 - (i ^ 1)] += num;
      mxflow += num;
      if (!num) dep[y] = -1;
    }
  }
  return mxflow;
}
bool flag[2005][2005];
int cont[NR];
int main() {
  n1 = read(), n2 = read(), m = read();
  T = n1 + n2 + 1;
  for (int i = 1, x, y; i <= m; i++) {
    x = read(), y = read();
    rd[x]++, rd[y + n1]++;
    u[i] = x, v[i] = y + n1;
  }
  for (int i = 1; i <= n1 + n2; i++) Min(mn, rd[i]);
  if (!mn) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= n1; i++) add(S, i, rd[i] - mn), add(i, S, 0);
  for (int i = 1; i <= n2; i++)
    add(i + n1, T, rd[i + n1] - mn), add(T, i + n1, 0);
  for (int i = 1; i <= m; i++) add(u[i], v[i], 1), add(v[i], u[i], 0);
  for (int x = mn; x >= 0; x--) {
    while (bfs()) dinic(S, INF);
    for (int i = n1 * 2 + n2 * 2 + 1; i < tot; i += 2)
      if (val[i]) flag[x][(i - n1 * 2 - n2 * 2 + 1) / 2] = 1, cont[x]++;
    for (int i = 1; i <= n1 * 2 + n2 * 2; i += 2) val[i]++;
  }
  for (int i = 0; i <= mn; i++) {
    printf("%d ", cont[i]);
    for (int j = 1; j <= m; j++)
      if (flag[i][j]) printf("%d ", j);
    puts("");
  }
  return 0;
}