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 = 2005, INF = 0x3f3f3f3f;
template <size_t N, size_t M, typename T>
struct Dinic {
  int n, s, t;
  T dist[N];
  struct Edge {
    int from, to;
    T cap, flow;
    Edge* next;
  } * edges[N], pool[M], *alloc, *curr[N];
  void init(int n, int s, int t) {
    this->n = n, this->s = s, this->t = t;
    alloc = pool;
    memset(edges, 0, sizeof edges);
  }
  Edge* new_Edge(int from, int to, T cap) {
    Edge* ret = alloc++;
    ret->from = from, ret->to = to;
    ret->cap = cap, ret->flow = 0;
    ret->next = edges[from];
    return ret;
  }
  Edge* rev(Edge* e) {
    Edge* ret = pool + ((e - pool) ^ 1);
    return ret;
  }
  void add_edge(int from, int to, T cap) {
    edges[from] = new_Edge(from, to, cap);
    edges[to] = new_Edge(to, from, 0);
  }
  bool bfs() {
    fill(dist, dist + n + 1, INF);
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int x = q.front();
      for (auto i = edges[x]; i; i = i->next)
        if (dist[i->to] > dist[x] + 1 && i->flow < i->cap) {
          dist[i->to] = dist[x] + 1;
          if (i->to == t) return true;
          q.push(i->to);
        }
      q.pop();
    }
    return false;
  }
  T dfs(int x, T rest) {
    if (x == t || rest == 0) return rest;
    T flow = 0;
    for (auto& i = curr[x]; i; i = i->next) {
      if (dist[i->to] != dist[x] + 1) continue;
      T temp = dfs(i->to, min(rest, i->cap - i->flow));
      if (temp > 0) {
        i->flow += temp, rev(i)->flow -= temp;
        flow += temp, rest -= temp;
        if (rest == 0) break;
      }
    }
    return flow;
  }
  T solve() {
    T flow = 0;
    while (bfs()) {
      for (int i = 0; i <= n; i++) curr[i] = edges[i];
      flow += dfs(s, INF);
    }
    return flow;
  }
};
int n[2], m;
int deg[MAXN * 2];
pair<int, int> e[MAXN];
Dinic<MAXN * 2, MAXN * 10, int> mf;
int main() {
  scanf("%d%d%d", n, n + 1, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &e[i].first, &e[i].second);
    deg[e[i].first]++;
    deg[n[0] + e[i].second]++;
  }
  int k = m;
  for (int i = 1; i <= n[0] + n[1]; i++) k = min(k, deg[i]);
  int s = 0, t = n[0] + n[1] + 1, S = t + 1, T = t + 2;
  for (int j = 0; j <= k; j++) {
    mf.init(n[0] + n[1] + 3, S, T);
    for (int i = 1; i <= m; i++) mf.add_edge(e[i].first, n[0] + e[i].second, 1);
    for (int i = 1; i <= n[0]; i++) mf.add_edge(s, i, INF);
    for (int i = 1; i <= n[1]; i++) mf.add_edge(n[0] + i, t, INF);
    mf.add_edge(t, s, INF);
    for (int i = 1; i <= n[0]; i++) mf.add_edge(S, i, j);
    for (int i = 1; i <= n[1]; i++) mf.add_edge(n[0] + i, T, j);
    mf.add_edge(s, T, j * n[0]);
    mf.add_edge(S, t, j * n[1]);
    mf.solve();
    for (auto i = mf.alloc - 1; i >= mf.pool + (n[0] + n[1] + m) * 2; i--)
      mf.edges[i->from] = i->next;
    mf.s = t, mf.t = s;
    mf.solve();
    vector<int> ans;
    for (int i = 1; i <= m; i++) {
      auto e = mf.pool + (i - 1) * 2;
      if (e->flow) ans.push_back(i);
    }
    printf("%d", (int)ans.size());
    for (auto i : ans) printf(" %d", i);
    printf("\n");
  }
  return 0;
}