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 INF = INT_MAX;
const int MN = 4005, ME = 10 * MN;
int src, snk, nno, ned;
int q[MN], fin[MN], pro[MN], dist[MN];
int flow[2 * ME], cap[2 * ME];
int sig[2 * ME], to[2 * ME];
inline void init(int _src, int _snk, int _n) {
  src = _src, snk = _snk, nno = _n, ned = 0;
  memset(fin, -1, sizeof(fin));
}
inline void add(int u, int v, int c) {
  to[ned] = v, cap[ned] = c, flow[ned] = 0, sig[ned] = fin[u], fin[u] = ned++;
  to[ned] = u, cap[ned] = 0, flow[ned] = 0, sig[ned] = fin[v], fin[v] = ned++;
}
inline void reset(int _src, int _snk) {
  src = _src, snk = _snk;
  for (int i = 0; i < ned; i++) flow[i] = 0;
}
bool bfs() {
  int st, en, u, v;
  memset(dist, -1, sizeof(dist));
  dist[src] = st = en = 0;
  q[en++] = src;
  while (st < en) {
    u = q[st++];
    for (int e = fin[u]; e >= 0; e = sig[e]) {
      v = to[e];
      if (flow[e] < cap[e] && dist[v] == -1) {
        dist[v] = dist[u] + 1;
        q[en++] = v;
      }
    }
  }
  return dist[snk] != -1;
}
int dfs(int u, int mn) {
  if (u == snk) return mn;
  int au, v;
  for (int &e = pro[u]; e >= 0; e = sig[e]) {
    v = to[e];
    if (flow[e] < cap[e] && dist[v] == dist[u] + 1)
      if (au = dfs(v, min(mn, cap[e] - flow[e]))) {
        flow[e] += au;
        flow[e ^ 1] -= au;
        return au;
      }
  }
  return 0;
}
long long dinitz() {
  long long f = 0;
  int au;
  while (bfs()) {
    for (int i = 0; i <= nno; i++) pro[i] = fin[i];
    while (au = dfs(src, INF)) f += au;
  }
  return f;
}
int n1, n2, m, pos[MN], ud[MN], vd[MN], fsz, sd, td, degu[MN], degv[MN];
int s, ss, t, tt;
void solve(int k) {
  int i = 0, j = m;
  while (i < j) {
    int m = (i + j) / 2;
    cap[fsz] = m;
    reset(ss, tt);
    if (dinitz() == k * (n1 + n2))
      j = m;
    else
      i = m + 1;
  }
  cap[fsz] = j;
  reset(ss, tt);
  dinitz();
  int t = 0;
  cout << j;
  for (int i = 0; i < int(m); i++)
    if (flow[pos[i]]) cout << " " << i + 1;
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n1 >> n2 >> m;
  s = n1 + n2, t = s + 1, ss = t + 1, tt = ss + 1;
  init(ss, tt, tt);
  for (int i = 0; i < int(n1); i++) {
    add(s, i, INF);
    ud[i] = ned;
    add(ss, i, 0);
  }
  sd = ned;
  add(s, tt, 0);
  for (int i = 0; i < int(n2); i++) {
    add(n1 + i, t, INF);
    vd[i] = ned;
    add(n1 + i, tt, 0);
  }
  td = ned;
  add(ss, t, 0);
  for (int i = 0; i < int(m); i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    degu[u]++;
    degv[v]++;
    pos[i] = ned;
    add(u, n1 + v, 1);
  }
  fsz = ned;
  add(t, s, m);
  int mn = m;
  for (int i = 0; i < int(n1); i++) mn = min(mn, degu[i]);
  for (int i = 0; i < int(n2); i++) mn = min(mn, degv[i]);
  for (int k = 0; k < int(mn + 1); k++) {
    solve(k);
    for (int i = 0; i < int(n1); i++) cap[ud[i]]++;
    cap[sd] += n1;
    for (int i = 0; i < int(n2); i++) cap[vd[i]]++;
    cap[td] += n2;
  }
  return 0;
}