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;
struct edge {
  int end, last, vol;
};
int N = 0, M = 0, R = 0, cnt = 0, _cnt = 0;
int deg[2005 << 1] = {}, head[2005 << 1] = {}, _head[2005 << 1] = {},
                step[2005 << 1] = {}, current[2005 << 1] = {};
edge road[2005 << 3] = {};
void add_edge(int le, int ri) {
  ++deg[le], ++deg[ri];
  road[cnt].end = ri, road[cnt].last = head[le], road[cnt].vol = 1;
  ++cnt;
  road[cnt].end = le, road[cnt].last = head[ri], road[cnt].vol = 0;
  ++cnt;
  head[le] = cnt - 2, head[ri] = cnt - 1;
}
bool BFS() {
  queue<int> test;
  test.push(0);
  memset(step, -1, sizeof(step));
  step[0] = 0;
  while (!test.empty()) {
    int temp = test.front();
    test.pop();
    for (int ptr = head[temp]; ptr != -1; ptr = road[ptr].last) {
      if (road[ptr].vol <= 0 || step[road[ptr].end] != -1) continue;
      step[road[ptr].end] = step[temp] + 1;
      if (road[ptr].end == 2005)
        return true;
      else
        test.push(road[ptr].end);
    }
  }
  return false;
}
int DFS(int id, int sup) {
  if (id == 2005) return sup;
  for (int i = current[id]; i != -1; i = road[i].last) {
    int next = road[i].end;
    current[id] = i;
    if (step[next] != step[id] + 1 || road[i].vol <= 0) continue;
    int flow = DFS(next, min(sup, road[i].vol));
    if (flow) {
      road[i].vol -= flow;
      road[i ^ 1].vol += flow;
      return flow;
    }
  }
  return 0;
}
int Dinic() {
  int ans = 0;
  while (BFS()) {
    int flow = 0;
    for (int i = 0; i <= N; i++) current[i] = head[i];
    for (int i = 0; i <= M; i++) current[i + 2005] = head[i + 2005];
    while (bool(flow = DFS(0, (1 << 30)))) ans += flow;
  }
  return ans;
}
int main() {
  int le = 0, ri = 0, MIN = 2005;
  scanf("%d%d%d", &N, &M, &R);
  memset(head, -1, sizeof(head));
  while (R--) {
    scanf("%d%d", &le, &ri);
    add_edge(le, ri + 2005);
  }
  for (int i = 1; i <= N; i++) MIN = min(MIN, deg[i]);
  for (int i = 1; i <= M; i++) MIN = min(MIN, deg[2005 + i]);
  _cnt = cnt;
  memcpy(_head, head, sizeof(head));
  for (int ans = 0; ans <= MIN; ans++) {
    cnt = _cnt;
    memcpy(head, _head, sizeof(head));
    for (int i = 1; i <= N; i++) {
      road[cnt].end = i, road[cnt].last = head[0], road[cnt].vol = deg[i] - ans;
      ++cnt;
      road[cnt].end = 0, road[cnt].last = head[i], road[cnt].vol = 0;
      ++cnt;
      head[0] = cnt - 2, head[i] = cnt - 1;
    }
    for (int i = 1; i <= M; i++) {
      road[cnt].end = 2005, road[cnt].last = head[i + 2005],
      road[cnt].vol = deg[2005 + i] - ans;
      ++cnt;
      road[cnt].end = 2005 + i, road[cnt].last = head[2005], road[cnt].vol = 0;
      ++cnt;
      head[2005 + i] = cnt - 2, head[2005] = cnt - 1;
    }
    int res = Dinic(), num = 0;
    for (int i = 0; i < _cnt; i += 2)
      if (road[i].vol == 1) ++num;
    printf("%d", num);
    for (int i = 0; i < _cnt; i += 2) {
      if (road[i].vol == 1) printf(" %d", (i >> 1) + 1);
      road[i].vol = 1;
      road[i ^ 1].vol = 0;
    }
    printf("\n");
  }
  return 0;
}