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;
template <typename T>
string tos(T a) {
  stringstream ss;
  string ret;
  ss << a;
  ss >> ret;
  return ret;
}
void read(int &_a) { int temp = scanf("%d", &_a); }
void read(int &_a, int &_b) { int temp = scanf("%d %d", &_a, &_b); }
void read(int &_a, int &_b, int &_c) {
  int temp = scanf("%d %d %d", &_a, &_b, &_c);
}
const int SZ = 4007;
int na, nb, m;
set<pair<int, int> > egs;
vector<int> ANS[SZ];
vector<int> ag[SZ], GM[SZ];
int cap[SZ][SZ], deg[SZ], P[SZ];
queue<int> Q;
int dinic(int source, int sink) {
  int ret = 0;
  while (true) {
    while (!Q.empty()) Q.pop();
    memset(P, -1, sizeof P);
    ;
    P[source] = source;
    Q.push(source);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (int(i) = (0); (i) < (ag[u].size()); (i)++) {
        int v = ag[u][i];
        if (P[v] == -1 && cap[u][v]) {
          P[v] = u;
          Q.push(v);
        }
      }
    }
    if (P[sink] == -1) break;
    for (int(x) = (0); (x) < (ag[sink].size()); (x)++) {
      int z = ag[sink][x];
      if (cap[z][sink] && P[z] != -1) {
        int bot = cap[z][sink];
        int now = z;
        while (true) {
          if (now == source) break;
          int u = P[now];
          bot = min(bot, cap[u][now]);
          if (!bot) break;
          now = u;
        }
        if (!bot) continue;
        now = z;
        cap[z][sink] -= bot;
        cap[sink][z] += bot;
        while (true) {
          if (now == source) break;
          int u = P[now];
          cap[u][now] -= bot;
          cap[now][u] += bot;
          now = u;
        }
        ret += bot;
      }
    }
  }
  return ret;
}
map<pair<int, int>, int> egtoind;
int iegtoind;
int main() {
  while (cin >> na >> nb >> m) {
    memset(cap, 0, sizeof cap);
    ;
    memset(deg, 0, sizeof deg);
    ;
    egs.clear();
    for (int(i) = (0); (i) < (SZ); (i)++) {
      ag[i].clear();
      ANS[i].clear();
      GM[i].clear();
    }
    egtoind.clear();
    iegtoind = 0;
    for (int(i) = (0); (i) < (m); (i)++) {
      int u, v;
      read(u, v);
      v += na;
      egs.insert(make_pair(u, v));
      int xind = -1;
      if (egtoind.find(make_pair(u, v)) == egtoind.end()) {
        xind = iegtoind++;
        egtoind[make_pair(u, v)] = xind;
      } else
        xind = egtoind[make_pair(u, v)];
      GM[xind].push_back(i + 1);
      cap[u][v]++;
      deg[u]++;
      deg[v]++;
    }
    int k = SZ;
    int sink = na + nb + 1;
    for (int(i) = (1); (i) < (na + 1); (i)++) k = min(k, deg[i]);
    for (int(i) = (na + 1); (i) < (sink); (i)++) k = min(k, deg[i]);
    for (int(i) = (1); (i) < (na + 1); (i)++) {
      ag[0].push_back(i);
      ag[i].push_back(0);
      cap[0][i] = deg[i] - k;
    }
    for (int(i) = (na + 1); (i) < (sink); (i)++) {
      ag[i].push_back(sink);
      ag[sink].push_back(i);
      cap[i][sink] = deg[i] - k;
    }
    for (int(i) = (0); (i) < (sink + 1); (i)++)
      for (int(j) = (i + 1); (j) < (sink + 1); (j)++)
        if (cap[i][j] || cap[j][i]) {
          ag[i].push_back(j);
          ag[j].push_back(i);
        }
    int lp = k;
    for (int(x) = (0); (x) < (lp + 1); (x)++) {
      dinic(0, sink);
      for (__typeof__(egs.begin()) it = egs.begin(); it != egs.end(); it++) {
        int u = it->first;
        int v = it->second;
        int xind = egtoind[make_pair(u, v)];
        for (int(j) = (0); (j) < (cap[u][v]); (j)++) {
          int ind = GM[xind][j];
          ANS[k].push_back(ind);
        }
      }
      k--;
      for (int(i) = (1); (i) < (na + 1); (i)++) cap[0][i]++;
      for (int(i) = (na + 1); (i) < (sink); (i)++) cap[i][sink]++;
    }
    for (int(x) = (0); (x) < (lp + 1); (x)++) {
      int alen = ANS[x].size();
      printf("%d", alen);
      for (int(i) = (0); (i) < (alen); (i)++) printf(" %d", ANS[x][i]);
      puts("");
    }
  }
  return 0;
}