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;
inline int read() {
  char ch = getchar();
  int x = 0, f = 1;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int maxn = 1e5 + 100;
const int inf = 0x3f3f3f3f;
const int mod = 9209;
const int bas = 131;
int head[maxn], ver[maxn << 2], edge[maxn << 2], Next[maxn << 2], d[maxn << 2],
    id[maxn << 2];
int n, m, s, t, tot, maxflow;
queue<int> q;
void add(int x, int y, int z, int i) {
  ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot,
  id[tot] = i;
  ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot,
  id[tot] = i;
}
bool bfs() {
  memset(d, 0, sizeof d);
  while (!q.empty()) q.pop();
  q.push(s);
  d[s] = 1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i; i = Next[i]) {
      if (edge[i] && !d[ver[i]]) {
        q.push(ver[i]);
        d[ver[i]] = d[x] + 1;
        if (ver[i] == t) return 1;
      }
    }
  }
  return 0;
}
int dinic(int x, int flow) {
  if (x == t) return flow;
  int rest = flow, k;
  for (int i = head[x]; i && rest; i = Next[i]) {
    if (edge[i] && d[ver[i]] == d[x] + 1) {
      k = dinic(ver[i], min(rest, edge[i]));
      if (!k) d[ver[i]] = 0;
      edge[i] -= k;
      edge[i ^ 1] += k;
      rest -= k;
    }
  }
  return flow - rest;
}
char ss[maxn];
int dd[maxn];
vector<int> G[maxn];
int main() {
  int n1, n2;
  scanf("%d %d %d", &n1, &n2, &m);
  memset(head, 0, sizeof head);
  s = 0, t = n1 + n2 + 1;
  tot = 1;
  for (int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    add(x, y + n1, 1, i);
    dd[x]++;
    dd[y + n1]++;
  }
  int mind = inf;
  for (int i = 1; i <= n1; i++) mind = min(mind, dd[i]);
  for (int i = 1; i <= n2; i++) mind = min(mind, dd[n1 + i]);
  for (int i = 1; i <= n1; i++)
    if (dd[i] - mind) add(s, i, dd[i] - mind, 0);
  for (int i = 1; i <= n2; i++)
    if (dd[i + n1] - mind) add(i + n1, t, dd[i + n1] - mind, 0);
  for (int i = mind; i >= 0; i--) {
    int flow = 0;
    while (bfs()) {
      while (flow = dinic(s, inf)) maxflow += flow;
    }
    for (int j = 3; j <= tot; j += 2)
      if (ver[j] >= 1 && ver[j] <= n1 && !edge[j]) G[i].push_back(id[j]);
    for (int j = 1; j <= n1; j++) add(s, j, 1, 0);
    for (int j = 1; j <= n2; j++) add(j + n1, t, 1, 0);
  }
  for (int i = 0; i <= mind; i++) {
    printf("%d ", G[i].size());
    for (int j = 0; j < G[i].size(); j++) printf("%d ", G[i][j]);
    printf("\n");
  }
}