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;
using ll = long long;
struct EdgeI {
  int i, rev;
};
struct Edge {
  int from, to;
  ll cap, use;
  int op(int i) { return i == from ? to : from; }
  int co(int i) { return i == from ? cap : use; }
};
vector<Edge> edges(6000, (Edge){0, 0, 0, 0});
struct Dinic {
  int size;
  vector<vector<EdgeI>> g;
  ll inf;
  Dinic(int size, ll inf = 1e18) : size(size), g(size), inf(inf) {}
  void addEdge(int a, int b, ll cap, int i) {
    edges[i] = (Edge){a, b, cap, 0};
    g[a].emplace_back((EdgeI){i, (int)g[b].size()});
    g[b].emplace_back((EdgeI){i, (int)g[a].size() - 1});
  }
  ll solve(int s, int t) {
    ll flow = 0;
    while (1) {
      vector<int> used(size, 0);
      ll x = dfs(used, s, t, inf);
      if (x == 0) break;
      flow += x;
      if (flow >= inf) return inf;
    }
    return flow;
  }

 private:
  ll dfs(vector<int> &used, int v, int t, ll m) {
    if (v == t) return m;
    used[v] = 1;
    for (EdgeI info : g[v])
      if (!used[edges[info.i].op(v)] && edges[info.i].co(v) > 0) {
        ll d =
            dfs(used, edges[info.i].op(v), t, min(m, (ll)edges[info.i].co(v)));
        if (d == 0) continue;
        int tt = edges[info.i].from == v ? 1 : -1;
        edges[info.i].cap -= d * tt;
        edges[info.i].use += d * tt;
        return d;
      }
    return 0;
  }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n1, n2, m;
  cin >> n1 >> n2 >> m;
  int n = n1 + n2;
  vector<int> d1(n1), d2(n2);
  Dinic ecasdqina(n + 2);
  map<pair<int, int>, vector<int>> es;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    d1[a]++;
    d2[b]++;
    es[make_pair(a, b)].emplace_back(i);
  }
  int k = 0;
  for (auto el : es) {
    ecasdqina.addEdge(el.first.first, n1 + el.first.second, el.second.size(),
                      k++);
  }
  int s = n, t = s + 1;
  for (int i = 0; i < n1; i++) {
    int ii = m + i;
    ecasdqina.addEdge(s, i, 0, ii);
  }
  for (int i = 0; i < n2; i++) {
    int ii = m + n1 + i;
    ecasdqina.addEdge(n1 + i, t, 0, ii);
  }
  int deg = 1e9;
  for (int i = 0; i < n1; i++) deg = min(deg, d1[i]);
  for (int i = 0; i < n2; i++) deg = min(deg, d2[i]);
  vector<set<int>> ans(deg + 2);
  vector<int> bef(2000);
  for (int i = deg; i >= 1; i--) {
    for (int j = 0; j < n1; j++) {
      int ii = m + j;
      ll &cap = edges[ii].cap;
      ll use = edges[ii].use;
      cap += (d1[j] - i) - (cap + use);
    }
    for (int j = 0; j < n2; j++) {
      int ii = m + n1 + j;
      ll &cap = edges[ii].cap;
      ll use = edges[ii].use;
      cap += (d2[j] - i) - (cap + use);
    }
    for (int j = 0; j < 6000; j++) {
      ll &cap = edges[j].cap;
      ll &use = edges[j].use;
      cap = cap + use;
      use = 0;
    }
    ecasdqina.solve(s, t);
    int j = 0;
    for (auto el : es) {
      for (int k = 0; k < edges[j].use; k++) {
        ans[i].emplace(el.second[k]);
      }
      j++;
    }
  }
  cout << 0 << endl;
  for (int i = 1; i <= deg; i++) {
    cout << m - ans[i].size();
    for (int j = 0; j < m; j++)
      if (!ans[i].count(j)) cout << " " << j + 1;
    cout << endl;
  }
}