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;
long long MOD = 12345678910;
long long POW(long long a, long long b, long long MMM = MOD) {
  long long ret = 1;
  for (; b; b >>= 1, a = (a * a) % MMM)
    if (b & 1) ret = (ret * a) % MMM;
  return ret;
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) {
  if (a == 0 || b == 0) return a + b;
  return a * (b / gcd(a, b));
}
int dx[] = {0, -1, 1, 0}, dy[] = {1, 0, 0, -1};
int ddx[] = {0, 0, 1, 1, 1, -1, -1, -1}, ddy[] = {1, -1, 1, 0, -1, 1, 0, -1};
struct Edge {
  int to, r, c, idx;
  Edge *ori;
  Edge *rev;
  Edge(int T, int R, int C, int I) { to = T, r = R, c = C, idx = I; }
};
vector<Edge *> v[4002];
void addedge(int f, int t, int r, int c, int i) {
  Edge *ori = new Edge(t, r, c, i);
  Edge *rev = new Edge(f, 0, -c, i);
  ori->rev = rev;
  rev->rev = ori;
  v[f].push_back(ori);
  v[t].push_back(rev);
}
const int S = 4000, T = 4001;
int level[4002], work[4002];
bool bfs() {
  memset(level, -1, sizeof(level));
  ;
  level[S] = 0;
  queue<int> q;
  q.push(S);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (auto &nn : v[x]) {
      int next = nn->to;
      if (level[next] == -1 && nn->r > 0) {
        level[next] = level[x] + 1;
        q.push(next);
      }
    }
  }
  return level[T] != -1;
}
int dfs(int N, int des, int flow) {
  if (N == des) return flow;
  for (int &i = work[N]; i < v[N].size(); i++) {
    int next = v[N][i]->to;
    if (level[next] == level[N] + 1 && v[N][i]->r > 0) {
      int df = dfs(next, des, min(v[N][i]->r, flow));
      if (df > 0) {
        v[N][i]->r -= df;
        v[N][i]->rev->r += df;
        return df;
      }
    }
  }
  return 0;
}
pair<int, int> edge[2001];
int cnt[4000], c[4000];
bool chk[2001];
int main() {
  int n1, n2, m;
  scanf("%d%d%d", &n1, &n2, &m);
  for (int(i) = (0); (i) <= (n1 - 1); (i) += (1)) addedge(S, i, 0, 0, -1);
  for (int(i) = (n1); (i) <= (n1 + n2 - 1); (i) += (1)) addedge(i, T, 0, 0, -1);
  for (int(i) = (1); (i) <= (m); (i) += (1)) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--, y--;
    edge[i] = make_pair(x, n1 + y);
    addedge(x, n1 + y, 1, 0, i);
    cnt[x]++;
    cnt[n1 + y]++;
  }
  int K = *min_element(cnt, cnt + n1 + n2);
  puts("0");
  for (int(k) = (1); (k) <= (K); (k) += (1)) {
    for (auto &E : v[S]) E->r++;
    for (auto &E : v[T]) E->rev->r++;
    memset(c, 0, sizeof(c));
    ;
    memset(chk, 0, sizeof(chk));
    ;
    while (bfs()) {
      memset(work, 0, sizeof(work));
      ;
      while (1) {
        int f = dfs(S, T, 987654321);
        if (f == 0) break;
      }
    }
    vector<int> ans;
    for (int(i) = (0); (i) <= (n1 - 1); (i) += (1)) {
      for (auto &E : v[i]) {
        if (E->to != S && E->r == 0) {
          ans.push_back(E->idx);
          chk[E->idx] = 1;
          c[i]++, c[E->to]++;
        }
      }
    }
    for (int(i) = (0); (i) <= (n1 + n2 - 1); (i) += (1)) {
      if (c[i] >= k) continue;
      for (auto &E : v[i]) {
        if (chk[E->idx]) continue;
        if (E->to != S && E->to != T) {
          ans.push_back(E->idx);
          chk[E->idx] = 1;
          c[i]++;
          if (c[i] == k) break;
        }
      }
    }
    printf("%d ", ans.size());
    for (int x : ans) printf("%d ", x);
    puts("");
  }
}