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;
int n, n1, n2, m, k;
vector<int> w, to, sz;
vector<vector<int>> g, ans;
int s, t;
vector<int> vis, pre;
queue<int> q;
bool bfs() {
  while (!q.empty()) q.pop();
  for (int i = 0; i < n; i++) vis[i] = 0;
  vis[t] = 0;
  vis[s] = 1;
  q.push(s);
  int x;
  while (!q.empty()) {
    x = q.front(), q.pop();
    for (const auto &i : g[x]) {
      if (!vis[to[i]] && w[i]) {
        vis[to[i]] = 1;
        pre[to[i]] = i;
        q.push(to[i]);
        if (to[i] == t) return true;
      }
    }
  }
  return false;
}
void update() {
  for (const auto &i : g[s]) w[i]++;
  for (const auto &i : g[t]) w[i ^ 1]++;
}
void augment() {
  static int at;
  at = t;
  while (at != s) {
    w[pre[at]]--;
    w[pre[at] ^ 1]++;
    at = to[pre[at] ^ 1];
  }
}
void work() {
  while (bfs()) augment();
  ans.push_back(vector<int>());
  for (int i = 0; i < 2 * m; i += 2)
    if (w[i]) ans.back().push_back(1 + i / 2);
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n1 >> n2 >> m;
  n = n1 + n2;
  s = n;
  t = n + 1;
  g.resize(n + 2);
  sz.resize(n);
  for (int i = 0, u, v; i < m; i++) {
    cin >> u >> v;
    --u, --v;
    v += n1;
    g[u].push_back(w.size());
    w.push_back(1);
    to.push_back(v);
    g[v].push_back(w.size());
    w.push_back(0);
    to.push_back(u);
  }
  for (int i = 0; i < n; i++) sz[i] = g[i].size();
  k = *min_element(sz.begin(), sz.end());
  for (int i = 0; i < n1; i++) {
    g[s].push_back(w.size());
    w.push_back(sz[i] - k);
    to.push_back(i);
    g[i].push_back(w.size());
    w.push_back(0);
    to.push_back(s);
  }
  for (int i = n1; i < n; i++) {
    g[i].push_back(w.size());
    w.push_back(sz[i] - k);
    to.push_back(t);
    g[t].push_back(w.size());
    w.push_back(0);
    to.push_back(i);
  }
  vis.resize(n + 2);
  pre.resize(n + 2);
  for (; k >= 0; k--) work(), update();
  for (int i = ans.size() - 1; i >= 0; i--) {
    cout << ans[i].size() << " ";
    for (const auto &j : ans[i]) cout << j << " ";
    cout << '\n';
  }
}