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;
class MaxFlow {
 public:
  map<long long, map<long long, long long> > adj;
  long long source, sink, flow;
  MaxFlow(long long source, long long sink)
      : source(source), sink(sink), flow(0) {}
  void add_edge(long long st, long long en, long long cap = 1) {
    adj[st][en] += cap;
    assert(cap >= 0);
    if (!adj[en].count(st)) adj[en][st] = 0;
  }
  long long Flow() {
    while (1) {
      map<long long, long long> prev;
      prev[source] = source;
      queue<long long> q;
      q.push(source);
      bool foundsink = false;
      while (!foundsink && q.size()) {
        long long top = q.front();
        q.pop();
        for (auto &i : adj[top]) {
          if (i.second == 0 || prev.count(i.first)) continue;
          prev[i.first] = top;
          q.push(i.first);
          if (i.first == sink) {
            foundsink = true;
            break;
          }
        }
      }
      if (foundsink) {
        long long curr = sink;
        long long minc = adj[prev[sink]][sink];
        while (curr != source) {
          long long &pcurr = prev[curr];
          minc = min(minc, adj[pcurr][curr]);
          curr = pcurr;
        }
        curr = sink;
        assert(minc != 0);
        while (curr != source) {
          long long &pcurr = prev[curr];
          adj[pcurr][curr] -= minc;
          adj[curr][pcurr] += minc;
          curr = pcurr;
        }
        flow += minc;
      } else {
        break;
      }
    }
    return flow;
  }
};
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n1, n2, m, x, y;
  cin >> n1 >> n2 >> m;
  long long source = 0, sink = ((n1) + (n2)) + 1;
  MaxFlow f(source, sink);
  vector<long long> degree(n1 + n2 + 10, 0);
  vector<pair<long long, long long> > edges;
  for (long long i = 0; i < m; i++) {
    cin >> x >> y;
    f.add_edge(((x)), ((n1) + (y)));
    degree[((x))]++;
    degree[((n1) + (y))]++;
    edges.push_back({((x)), ((n1) + (y))});
  }
  long long mindeg = degree[((1))];
  for (long long i = ((1)); i <= ((n1) + (n2)); i++)
    mindeg = min(mindeg, degree[i]);
  for (long long i = 1; i <= n1; i++)
    f.add_edge(source, ((i)), degree[((i))] - mindeg);
  for (long long i = 1; i <= n2; i++)
    f.add_edge(((n1) + (i)), sink, degree[((n1) + (i))] - mindeg);
  string s = "";
  vector<vector<long long> > v(mindeg + 1);
  while (mindeg >= 0) {
    f.Flow();
    map<pair<long long, long long>, long long> cnt;
    for (long long i = 0; i < m; i++) {
      cnt[edges[i]]++;
      if (f.adj[edges[i].first][edges[i].second] >= cnt[edges[i]]) {
        v[mindeg].push_back(i + 1);
      }
    }
    for (long long i = 1; i <= n1; i++) f.add_edge(source, ((i)), 1);
    for (long long i = 1; i <= n2; i++) f.add_edge(((n1) + (i)), sink, 1);
    mindeg--;
  }
  for (auto &i : v) {
    cout << i.size() << " ";
    for (auto &j : i) cout << j << " ";
    cout << '\n';
  }
  return 0;
}