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;
using ld = long double;
const ll inf = 1e9 + 7;
using pii = pair<ll, ll>;
template <typename T>
using vec = vector<T>;
struct edge {
  ll a, b, c, flow = 0, id;
  ll max1 = inf;
  edge() { a = 0, b = 0, c = 0; }
  edge(ll _a, ll _b, ll _c, ll _id, ll _max1 = inf) {
    a = _a, b = _b, c = _c;
    id = _id;
    max1 = _max1;
  }
};
vec<edge> e;
vec<vec<ll>> g;
void insert_edge(ll a, ll b, ll c, ll num, ll max1 = inf) {
  g[a].push_back(e.size());
  e.push_back(edge(a, b, c, num, max1));
  g[b].push_back(e.size());
  e.push_back(edge(b, a, 0, -1, max1));
}
vec<ll> d;
bool bfs(ll s, ll t, ll b) {
  ll n = g.size();
  d = vec<ll>(n, inf);
  queue<ll> q;
  q.push(s);
  d[s] = 0;
  while (!q.empty()) {
    ll v = q.front();
    q.pop();
    for (auto u : g[v]) {
      edge e1 = e[u];
      if (d[e1.b] == inf && e1.c - e1.flow >= b) {
        q.push(e1.b);
        d[e1.b] = d[e1.a] + 1;
      }
    }
  }
  return d[t] != inf;
}
vec<ll> ind, path;
bool dfs(ll s, ll t, ll b) {
  if (d[s] >= d[t]) return s == t;
  for (; ind[s] < g[s].size(); ++ind[s]) {
    edge e1 = e[g[s][ind[s]]];
    if (d[e1.b] == d[e1.a] + 1 && e1.c - e1.flow >= b && dfs(e1.b, t, b)) {
      path.push_back(g[s][ind[s]]);
      return true;
    }
  }
  return false;
}
void block() {
  ll minf = inf;
  for (auto elem : path) {
    minf = min(minf, e[elem].c - e[elem].flow);
  }
  for (auto elem : path) {
    e[elem].flow += minf;
    e[elem ^ 1].flow -= minf;
  }
  path.clear();
}
void maxflow(ll s, ll t, bool add) {
  for (ll b = (add ? 1 : (1 << 30)); b; b >>= 1) {
    while (bfs(s, t, b)) {
      ll n = g.size();
      ind = vec<ll>(n);
      while (dfs(s, t, b)) {
        block();
      }
    }
  }
}
void run() {
  ll n1, n2, m;
  cin >> n1 >> n2 >> m;
  vec<ll> deg1(n1), deg2(n2);
  ll N = 2 + n1 + n2;
  g.resize(N);
  vec<pii> edges;
  for (ll i = 0; i < m; ++i) {
    ll u, v;
    cin >> u >> v;
    --u, --v;
    edges.push_back({u, v});
    insert_edge(1 + u, 1 + v + n1, 1, i);
    deg1[u]++;
    deg2[v]++;
  }
  ll n0 = e.size();
  ll mindeg = min(*min_element(deg1.begin(), deg1.end()),
                  *min_element(deg2.begin(), deg2.end()));
  for (ll i = 0; i < n1; ++i) {
    insert_edge(0, i + 1, deg1[i] - mindeg, -2);
  }
  for (ll i = 0; i < n2; ++i) {
    insert_edge(1 + n1 + i, N - 1, deg2[i] - mindeg, -2);
  }
  vec<vec<ll>> ans;
  for (ll k = mindeg; k >= 0; k--) {
    maxflow(0, N - 1, k != mindeg);
    ans.push_back({});
    for (ll i = 0; i < n0; ++i) {
      if (e[i].id != -1 && e[i].flow == 0) {
        ans.back().push_back(e[i].id + 1);
      }
    }
    for (ll i = n0; i < e.size(); ++i) {
      if (e[i].id == -2) {
        e[i].c++;
      }
    }
  }
  reverse(ans.begin(), ans.end());
  for (auto elem : ans) {
    cout << elem.size() << ' ';
    for (auto t : elem) {
      cout << t << ' ';
    }
    cout << '\n';
  }
}
int32_t main() { run(); }