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 MaximumFlow {
  static const int InfCapacity = 1e9;
  struct Edge {
    int to;
    int capacity;
    int rev;
    int id;
  };
  vector<vector<Edge> > g;
  void init(int n) { g.assign(n, vector<Edge>()); }
  void add(int i, int j, int capacity, int id) {
    Edge e, f;
    e.to = j, f.to = i;
    e.capacity = capacity, f.capacity = 0, e.id = id;
    g[i].push_back(e);
    g[j].push_back(f);
    g[i].back().rev = (int)g[j].size() - 1;
    g[j].back().rev = (int)g[i].size() - 1;
  }
  void addB(int i, int j, int capacity) {
    Edge e, f;
    e.to = j, f.to = i;
    e.capacity = capacity, f.capacity = capacity;
    g[i].push_back(e);
    g[j].push_back(f);
    g[i].back().rev = (int)g[j].size() - 1;
    g[j].back().rev = (int)g[i].size() - 1;
  }
  void solve(int sz, int maxx) {
    vector<Edge> v;
    for (int i = 1; i <= sz; i++) {
      for (auto x : g[i]) {
        Edge e = x;
        if (e.capacity == 0 && e.to > sz && e.to <= maxx) {
          v.push_back(e);
        }
      }
    }
    cout << v.size() << " ";
    vector<int> ans;
    for (auto x : v) {
      ans.push_back(x.id);
    }
    sort(ans.begin(), ans.end());
    for (auto x : ans) {
      cout << x << " ";
    }
    cout << endl;
  }
  int maximumFlow(int s, int t) {
    int n = g.size();
    vector<int> level(n);
    int total = 0;
    bool update;
    do {
      update = false;
      fill(level.begin(), level.end(), -1);
      level[s] = 0;
      queue<int> q;
      q.push(s);
      for (int d = n; !q.empty() && level[q.front()] < d;) {
        int u = q.front();
        q.pop();
        if (u == t) d = level[u];
        for (int kk = 0; kk < (int)g[u].size(); kk++) {
          Edge *e = &g[u][kk];
          if (e->capacity > 0 && level[e->to] == -1)
            q.push(e->to), level[e->to] = level[u] + 1;
        }
      }
      vector<int> iter(n);
      for (int i = 0; i < n; i++) iter[i] = (int)g[i].size() - 1;
      while (1) {
        int f = augment(level, iter, s, t, InfCapacity);
        if (f == 0) break;
        total += f;
        update = true;
      }
    } while (update);
    return total;
  }
  int augment(vector<int> &level, vector<int> &iter, int u, int t, int f) {
    if (u == t || f == 0) return f;
    int lv = level[u];
    if (lv == -1) return 0;
    level[u] = -1;
    for (; iter[u] >= 0; --iter[u]) {
      Edge &e = g[u][iter[u]];
      if (level[e.to] <= lv) continue;
      int l = augment(level, iter, e.to, t, min(f, e.capacity));
      if (l == 0) continue;
      e.capacity -= l;
      g[e.to][e.rev].capacity += l;
      level[u] = lv;
      return l;
    }
    return 0;
  }
};
int n1, n2, m;
int get_num(int x) { return n1 + x; }
int in[6005];
int main() {
  MaximumFlow My;
  My.init(6000);
  cin >> n1 >> n2 >> m;
  int ok = 0;
  if (n1 < n2) {
    ok = 1;
    swap(n1, n2);
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    if (ok) swap(x, y);
    in[x]++;
    y = get_num(y);
    in[y]++;
    My.add(x, y, 1, i + 1);
  }
  int minx = in[1];
  for (int i = 1; i <= n1 + n2; i++) {
    minx = min(minx, in[i]);
  }
  int st = n1 + n2 + 5;
  int st2 = st + 2;
  int En = st + 1;
  int En2 = En + 1;
  cout << 0 << endl;
  for (int j = 1; j <= n2; j++) {
    My.add(get_num(j), En2, 1e9, 0);
  }
  int cnt = 0;
  int dis = abs(n1 - n2);
  for (int i = 1; i <= minx; i++) {
    My.add(En2, En, dis, 0);
    for (int j = 1; j <= n1; j++) {
      My.add(st, j, 1, 0);
    }
    for (int j = 1; j <= n2; j++) {
      My.add(get_num(j), En, 1, 0);
    }
    My.maximumFlow(st, En);
    My.solve(n1, n1 + n2);
  }
}