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 rd() {
  long long x = 0, first = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') first = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * first;
}
const int INF = 0x3f3f3f3f;
class edge {
 public:
  int second, e, first;
  edge() {}
  edge(int second, int e, int first) : second(second), e(e), first(first) {}
};
vector<edge> Ve;
vector<int> conn[10050];
void epush(int second, int e, int first) {
  conn[second].push_back(Ve.size());
  conn[e].push_back(Ve.size() + 1);
  Ve.emplace_back(second, e, first);
  Ve.emplace_back(e, second, 0);
}
int in[2050][2];
int dis[10050];
int dchk[10050];
int pos[10050];
int DFS(int n, int snk, int C) {
  if (n == snk) return 1;
  dchk[n] = C;
  for (; pos[n] < conn[n].size(); pos[n]++) {
    int it = conn[n][pos[n]];
    edge &ed = Ve[it];
    if (ed.first == 0 || dchk[ed.e] == C || dis[ed.e] != dis[ed.second] + 1)
      continue;
    if (DFS(ed.e, snk, C)) {
      Ve[it].first--;
      Ve[it ^ 1].first++;
      return 1;
    }
  }
  return 0;
}
int getFlow(int src, int snk) {
  int i, j;
  vector<int> Vu;
  for (int i = 0; i <= snk; i++) dis[i] = INF, dchk[i] = 0, pos[i] = 0;
  dis[src] = 0;
  Vu.push_back(src);
  for (i = 0; i < Vu.size(); i++) {
    for (auto it : conn[Vu[i]]) {
      edge &ed = Ve[it];
      if (ed.first == 0 || dis[Ve[it].e] != INF) continue;
      dis[Ve[it].e] = dis[Ve[it].second] + 1;
      Vu.push_back(Ve[it].e);
    }
  }
  if (dis[snk] == INF) return 0;
  int first = 0;
  while (DFS(src, snk, first + 1)) first++;
  return first;
}
int deg[4050];
bool echk[2050];
vector<int> Vl[4050];
int main() {
  int N1 = rd(), N2 = rd(), M = rd(), i, j, k;
  for (int i = 1; i <= M; i++) {
    int t1 = rd(), t2 = rd();
    deg[t1]++, deg[N1 + t2]++;
    epush(t1, t2 + N1, 1);
    in[i][0] = t1;
    in[i][1] = t2;
  }
  int src = 0, snk = N1 + N2 + 1;
  for (int i = 1; i <= N1; i++) epush(src, i, 0);
  for (int i = 1; i <= N2; i++) epush(i + N1, snk, 0);
  int mn = INF;
  for (int i = 1; i <= N1 + N2; i++) mn = min(mn, deg[i]);
  puts("0");
  for (int q = 1; q <= mn; q++) {
    for (auto &it : Ve) {
      if (it.second == src) it.first++;
      if (it.e == snk) it.first++;
    }
    int first = 0, t;
    while (t = getFlow(src, snk)) first += t;
    for (int i = 1; i <= M; i++) echk[i] = false;
    vector<int> Va;
    for (int i = 0; i <= M - 1; i++)
      if (Ve[2 * i].first == 0) Va.push_back(i + 1), echk[i + 1] = true;
    for (int i = 1; i <= N1 + N2; i++) Vl[i].clear();
    for (int i = 1; i <= M; i++) {
      if (echk[i]) continue;
      Vl[in[i][0]].push_back(i);
      Vl[in[i][1] + N1].push_back(i);
    }
    for (auto &it : Ve) {
      if (it.second != src && it.e != snk) continue;
      int t = it.first;
      int n = it.e;
      if (it.e == snk) n = it.second;
      for (int i = 0; i < it.first; i++) Va.push_back(Vl[n][i]);
    }
    printf("%d ", Va.size());
    for (auto it : Va) printf("%d ", it);
    printf("\n");
  }
}