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;
const int maxn = 2 * 2e3 + 100;
const int base = 2000;
const int s = maxn - 2, t = maxn - 1;
const int inf = 1e9 + 100;
int head[maxn];
pair<int, int> ori[maxn];
int cnt = 1;
struct gg {
  int u, v, w, idx, next;
} side[maxn * 4];
void ins(int u, int v, int w, int idx) {
  side[++cnt] = (gg){u, v, w, idx, head[u]};
  head[u] = cnt;
  side[++cnt] = (gg){v, u, 0, idx, head[v]};
  head[v] = cnt;
}
int d[maxn];
vector<vector<int> > ans;
int cur[maxn], rk[maxn];
queue<int> q;
bool bfs() {
  memset(rk, 0, sizeof(rk));
  while (!q.empty()) q.pop();
  q.push(s);
  rk[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = side[i].next) {
      int v = side[i].v;
      if (rk[v] || !side[i].w) continue;
      rk[v] = rk[u] + 1;
      q.push(v);
    }
  }
  if (rk[t]) return 1;
  return 0;
}
int dfs(int u, int flow) {
  if (u == t || !flow) return flow;
  int tot = 0;
  for (int &i = cur[u]; i; i = side[i].next) {
    int v = side[i].v;
    if (side[i].w <= 0 || rk[v] != rk[u] + 1) continue;
    int sent = dfs(v, min(flow, side[i].w));
    flow -= sent, tot += sent;
    side[i].w -= sent, side[i ^ 1].w += sent;
    if (!flow) break;
  }
  return tot;
}
void dinic() {
  while (bfs()) {
    memcpy(cur, head, sizeof(head));
    dfs(s, inf);
  }
}
int n1, n2, m;
void debug() {
  for (int i = (1), iend = (n1); i <= iend; i++)
    for (int j = head[i]; j; j = side[j].next)
      cout << ">>" << side[j].u << ' ' << side[j].v << ' ' << side[j].w << endl;
  for (int i = (1), iend = (n2); i <= iend; i++)
    for (int j = head[i + base]; j; j = side[j].next)
      cout << ">>" << side[j].u << ' ' << side[j].v << ' ' << side[j].w << endl;
  for (int j = head[s]; j; j = side[j].next)
    cout << ">>" << side[j].u << ' ' << side[j].v << ' ' << side[j].w << endl;
  cout << "END" << endl;
}
int main() {
  ios::sync_with_stdio(0);
  cin >> n1 >> n2 >> m;
  int mi_d = 1e9, mx_d = 0;
  for (int i = (1), iend = (m); i <= iend; i++) {
    int u, v;
    cin >> u >> v;
    ori[i] = make_pair(u, v);
    d[u]++, d[v + base]++;
    ins(u, v + base, 1, i);
  }
  for (int i = (1), iend = (n1); i <= iend; i++)
    mi_d = min(mi_d, d[i]), mx_d = max(mx_d, d[i]);
  for (int i = (1), iend = (n2); i <= iend; i++)
    mi_d = min(mi_d, d[i + base]), mx_d = max(mx_d, d[i + base]);
  for (int i = (1), iend = (n1); i <= iend; i++) {
    ins(s, i, d[i] - mi_d - 1, 0);
  }
  for (int i = (1), iend = (n2); i <= iend; i++) {
    ins(i + base, t, d[i + base] - mi_d - 1, 0);
  }
  for (int k = mi_d; k >= 0; k--) {
    for (int i = head[s]; i; i = side[i].next) {
      if (!side[i].idx) side[i].w++;
    }
    for (int i = (1), iend = (n2); i <= iend; i++) {
      for (int j = head[i + base]; j; j = side[j].next) {
        int v = side[j].v;
        if (!side[j].idx && v == t) side[j].w++;
      }
    }
    dinic();
    vector<int> tmp;
    vector<int> jk;
    for (int gg = (base + 1), ggend = (base + n2); gg <= ggend; gg++)
      for (int i = head[gg]; i; i = side[i].next)
        if (side[i].idx && side[i].v <= n1 && side[i].w)
          tmp.push_back(side[i].idx);
    sort(tmp.begin(), tmp.end());
    int now = 0;
    for (int i = (1), iend = (m); i <= iend; i++) {
      if (now < tmp.size() && tmp[now] == i) {
        now++;
        continue;
      }
      jk.push_back(i);
    }
    ans.push_back(jk);
  }
  for (int i = ans.size() - 1; i >= 0; i--) {
    vector<int> tmp = ans[i];
    cout << tmp.size() << ' ';
    for (int j = (0), jend = (tmp.size() - 1); j <= jend; j++)
      cout << tmp[j] << ' ';
    cout << endl;
  }
  return 0;
}