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;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <class S, class T>
ostream& operator<<(ostream& os, const pair<S, T>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const unordered_set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream& operator<<(ostream& os, const unordered_map<S, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class S, class T>
ostream& operator<<(ostream& os, const map<S, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
void dbs(string str, T t) {
  cerr << str << " : " << t << "\n";
}
template <class T, class... S>
void dbs(string str, T t, S... s) {
  int idx = str.find(',');
  cerr << str.substr(0, idx) << " : " << t << ",";
  dbs(str.substr(idx + 1), s...);
}
template <class T>
void prc(T a, T b) {
  cerr << "[";
  for (T i = a; i != b; ++i) {
    if (i != a) cerr << ", ";
    cerr << *i;
  }
  cerr << "]\n";
}
int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) res = (res * x) % 1000000007;
    y = y / 2, x = (x * x) % 1000000007;
  }
  return res % 1000000007;
}
struct Edge {
  int u, v;
  int cap, flow;
  Edge() {}
  Edge(int _u, int _v, int _cap) : u(_u), v(_v), cap(_cap), flow(0) {}
};
struct Dinic {
  int N;
  vector<Edge> E;
  vector<vector<int>> g;
  vector<int> d, pt;
  Dinic(int _N) : N(_N), E(0), g(_N), d(_N), pt(_N) {}
  void AddEdge(int u, int v, int cap) {
    if (u != v) {
      E.emplace_back(Edge(u, v, cap));
      g[u].emplace_back(E.size() - 1);
      E.emplace_back(Edge(v, u, 0));
      g[v].emplace_back(E.size() - 1);
    }
  }
  bool BFS(int S, int T) {
    queue<int> q({S});
    fill(d.begin(), d.end(), N + 1);
    d[S] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u == T) break;
      for (int k : g[u]) {
        Edge& e = E[k];
        if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
          d[e.v] = d[e.u] + 1;
          q.emplace(e.v);
        }
      }
    }
    return d[T] != N + 1;
  }
  int DFS(int u, int T, int flow = -1) {
    if (u == T || flow == 0) return flow;
    for (int& i = pt[u]; i < g[u].size(); ++i) {
      Edge& e = E[g[u][i]];
      Edge& oe = E[g[u][i] ^ 1];
      if (d[e.v] == d[e.u] + 1) {
        int amt = e.cap - e.flow;
        if (flow != -1 && amt > flow) amt = flow;
        if (int pushed = DFS(e.v, T, amt)) {
          e.flow += pushed;
          oe.flow -= pushed;
          return pushed;
        }
      }
    }
    return 0;
  }
  int MaxFlow(int S, int T) {
    int total = 0;
    while (BFS(S, T)) {
      fill(pt.begin(), pt.end(), 0);
      while (int flow = DFS(S, T)) total += flow;
    }
    return total;
  }
};
int deg[50011];
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n1, n2, m, i;
  cin >> n1 >> n2 >> m;
  set<int> lol;
  map<pair<int, int>, vector<int>> haha;
  int mindegree = 10000;
  Dinic df(n1 + n2 + 2);
  for (i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    deg[u]++;
    deg[v + n1]++;
    haha[make_pair(u, v + n1)].push_back(i);
    lol.insert(i);
  }
  for (auto v : haha)
    df.AddEdge(v.first.first, v.first.second, v.second.size());
  for (i = 1; i <= n1 + n2; i++) mindegree = min(mindegree, deg[i]);
  int s = 0, t = n1 + n2 + 1;
  vector<vector<int>> ans(mindegree + 1);
  ;
  for (i = 1; i <= n1; i++) df.AddEdge(s, i, deg[i] - mindegree);
  for (i = n1 + 1; i <= n1 + n2; i++) df.AddEdge(i, t, deg[i] - mindegree);
  for (i = mindegree; i >= 0; i--) {
    df.MaxFlow(s, t);
    for (auto& vv : df.E) {
      if (vv.u >= 1 and vv.u <= n1) {
        vector<int> temp = haha[make_pair(vv.u, vv.v)];
        for (int j = 0; j < vv.flow; j++) ans[i].push_back(temp[j]);
      }
      if (vv.u == s) vv.cap++;
      if (vv.v == t) vv.cap++;
    }
  }
  for (i = 0; i <= mindegree; i++) {
    set<int> xxx = lol;
    for (auto v : ans[i]) xxx.erase(v);
    cout << xxx.size() << " ";
    for (auto v : xxx) cout << v << " ";
    cout << "\n";
  }
}