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;
struct Edge {
  long long to, flow, capacity;
  Edge* res;
  Edge(int to, long long capacity, long long cost = 0)
      : to(to), flow(0), capacity(capacity) {}
  void addFlow(long long flow) {
    this->flow += flow;
    this->res->flow -= flow;
  }
};
struct Dinic {
  vector<vector<Edge*>> adjList;
  vector<int> pos, dist;
  long long N;
  long long limit = 1;
  bool scaling;
  const long long INF = numeric_limits<long long>::max();
  Dinic(long long N, bool withScaling = false) : N(N), scaling(withScaling) {
    adjList.resize(N);
    pos.resize(N);
    dist.resize(N);
  }
  bool checkAns(int s) {
    for (auto e : adjList[s])
      if (e->flow != e->capacity) return false;
    return true;
  }
  vector<tuple<int, int, int>> getAns(int lim) {
    vector<tuple<int, int, int>> ans;
    for (int i = 0; i < lim; i++) {
      int u = 2 * i + 1;
      for (auto e : adjList[u]) {
        if (e->capacity == 0) continue;
        ans.emplace_back(i, e->to / 2 - lim, e->flow);
      }
    }
    return ans;
  }
  void addEdge(int u, int v, long long capacity, bool directed = false) {
    Edge* uv = new Edge(v, capacity);
    Edge* vu = new Edge(u, directed ? 0 : capacity);
    uv->res = vu;
    vu->res = uv;
    adjList[u].push_back(uv);
    adjList[v].push_back(vu);
  }
  long long BlockingFlow(int u, int t, long long flow) {
    if (u == t) return flow;
    for (int& i = pos[u]; i < (int)adjList[u].size(); i++) {
      Edge* E = adjList[u][i];
      if (E->capacity > E->flow && dist[E->to] == dist[u] + 1) {
        long long f = BlockingFlow(E->to, t, min(flow, E->capacity - E->flow));
        if (f > 0) {
          E->addFlow(f);
          return f;
        }
      }
    }
    return 0;
  }
  bool bfs(int s, int t) {
    fill(dist.begin(), dist.end(), -1);
    queue<long long> q;
    q.push(s);
    dist[s] = 0;
    while (!q.empty()) {
      long long u = q.front();
      q.pop();
      for (Edge* E : adjList[u]) {
        if (dist[E->to] == -1 && E->capacity > E->flow &&
            (!scaling || E->capacity - E->flow >= limit)) {
          dist[E->to] = dist[u] + 1;
          q.push(E->to);
        }
      }
    }
    return dist[t] != -1;
  }
  long long StartDinic(int s, int t) {
    long long maxFlow = 0;
    for (limit = (scaling ? 1 << 30 : 1); limit > 0; limit >>= 1) {
      dist[t] = 0;
      while (bfs(s, t)) {
        long long f = 0;
        fill(pos.begin(), pos.end(), 0);
        while ((f = BlockingFlow(s, t, INF))) {
          maxFlow += f;
        }
      }
    }
    return maxFlow;
  }
};
const int MAXN = 4e3 + 5;
const int INF = 1e6;
int n1, n2, m;
int degree[MAXN];
map<pair<int, int>, int> edges;
map<pair<int, int>, vector<int>> edges_list;
bool check(int x, int demand, Dinic*& dinic) {
  dinic = new Dinic(2 * (n1 + n2) + 4);
  int s, t, sp, tp;
  s = 2 * (n1 + n2);
  t = s + 1;
  sp = t + 1;
  tp = sp + 1;
  for (int u = 0; u < n1 + n2; u++) {
    dinic->addEdge(sp, 2 * u + 1, demand, true);
    dinic->addEdge(2 * u, tp, demand, true);
    dinic->addEdge(2 * u, 2 * u + 1, INF, true);
  }
  for (int u = 0; u < n1; u++) dinic->addEdge(s, 2 * u, INF, true);
  for (int u = n1; u <= n1 + n2 - 1; u++)
    dinic->addEdge(2 * u + 1, t, INF, true);
  for (const auto it : edges) {
    int u, v, c;
    tie(u, v) = it.first;
    c = it.second;
    dinic->addEdge(2 * u + 1, 2 * (n1 + v), c, true);
  }
  dinic->addEdge(t, s, x, true);
  dinic->StartDinic(sp, tp);
  return dinic->checkAns(sp);
}
int main() {
  cin >> n1 >> n2 >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    edges[make_pair(u, v)]++;
    edges_list[make_pair(u, v)].push_back(i);
    degree[u]++;
    degree[n1 + v]++;
  }
  cout << "0\n";
  for (int i = 1; i <= *min_element(degree, degree + n1 + n2); i++) {
    int l, r, mid;
    l = 0;
    r = m;
    Dinic* dinic;
    while (l < r) {
      mid = (l + r) >> 1;
      if (check(mid, i, dinic))
        r = mid;
      else
        l = mid + 1;
    }
    check(r, i, dinic);
    cout << r << ' ';
    auto ans = dinic->getAns(n1);
    for (auto e : ans) {
      int u, v, k;
      tie(u, v, k) = e;
      for (auto i : edges_list[make_pair(u, v)]) {
        if (k == 0) break;
        cout << i + 1 << ' ';
        k--;
      }
    }
    cout << '\n';
  }
  return 0;
}