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 N = 10001;
const int inf = INT_MAX;
namespace dinic {
struct edge {
  int v, p, c, i;
};
vector<edge> g[N];
int dis[N], cur[N], nc;
void adde(int u, int v, int c, int i) {
  g[u].push_back({v, (int)g[v].size(), c, i});
  g[v].push_back({u, (int)g[u].size() - 1, 0});
}
bool bfs(int s, int t) {
  fill_n(dis, nc, inf);
  queue<int> q;
  q.push(t);
  dis[t] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (edge e : g[u]) {
      int v = e.v;
      if (!g[v][e.p].c || dis[v] != inf) continue;
      dis[v] = dis[u] + 1;
      q.push(v);
    }
  }
  return dis[s] != inf;
}
int dfs(int u, int t, int f) {
  if (u == t) return f;
  int sf = 0;
  for (int& i = cur[u]; i < g[u].size(); ++i) {
    edge& e = g[u][i];
    int v = e.v;
    if (!e.c || dis[v] + 1 != dis[u]) continue;
    int df = dfs(v, t, min(e.c, f));
    e.c -= df;
    g[v][e.p].c += df;
    sf += df;
    f -= df;
    if (!f) break;
  }
  return sf;
}
int maxflow(int s, int t) {
  int sf = 0;
  while (bfs(s, t)) {
    fill_n(cur, nc, 0);
    sf += dfs(s, t, inf);
  }
  return sf;
}
}  // namespace dinic
int d1[N], d2[N];
using namespace dinic;
int main(void) {
  int n1, n2, m;
  scanf("%d %d %d", &n1, &n2, &m);
  nc = n1 + n2 + 2;
  int s = 0, t = nc - 1;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    adde(u, n1 + v, 1, i);
    d1[u]++;
    d2[v]++;
  }
  int k =
      min(*min_element(d1 + 1, d1 + n1 + 1), *min_element(d2 + 1, d2 + n2 + 1));
  for (int i = 1; i <= n1; ++i) adde(s, i, d1[i] - k, 0);
  for (int i = 1; i <= n2; ++i) adde(n1 + i, t, d2[i] - k, 0);
  vector<vector<int>> ans;
  for (int i = k; i >= 1; --i) {
    maxflow(s, t);
    ans.emplace_back();
    for (int u = 1; u <= n1; ++u)
      for (auto e : g[u])
        if (e.i && e.c) ans.back().push_back(e.i);
    for (auto& e : g[s]) e.c++;
    for (auto e : g[t]) g[e.v][e.p].c++;
  }
  ans.emplace_back();
  reverse(ans.begin(), ans.end());
  for (const auto& v : ans) {
    printf("%d", (int)v.size());
    for (int x : v) printf(" %d", x);
    printf("\n");
  }
  return 0;
}