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 Edge {
  Edge(int _to, int _cap, int _flow, int _id)
      : to(_to), cap(_cap), flow(_flow), id(_id) {}
  int to;
  int cap;
  int flow;
  int id;
};
class Graph {
 public:
  Graph(int n)
      : N(n + 100), vt(N), degrees(N, 0), maxDegree(0), minDegree(INT_MAX) {}
  void addEdge(int from, int to, int cap, int id) {
    vt[from].push_back(edges.size());
    edges.emplace_back(to, cap, 0, id);
    ++degrees[from];
    maxDegree = max(maxDegree, degrees[from]);
    vt[to].push_back(edges.size());
    edges.emplace_back(from, 0, 0, -3);
    ++degrees[to];
    maxDegree = max(maxDegree, degrees[to]);
  }
  void extendEdge(int idx, int inc = 0) {
    if (idx < 0 || idx >= edges.size()) {
      assert(0);
      return;
    }
    assert(inc >= 0);
    edges[idx].cap += inc;
  }
  int getMaxDegree() { return maxDegree; }
  vector<vector<int>>& getVT() { return vt; }
  vector<int>& getEdgesIncidentTo(int u) {
    assert(u >= 0 && u < N);
    return vt[u];
  }
  Edge& getEdge(int idx) {
    assert(idx >= 0 && idx < edges.size());
    return edges[idx];
  }
  vector<Edge>& getEdges() { return edges; }
  vector<int> getNotFullEdges() {
    vector<int> res;
    res.reserve(edges.size());
    for (auto& e : edges) {
      if (e.cap == e.flow || e.id < 0) {
        continue;
      }
      res.push_back(e.id);
    }
    return res;
  }
  vector<int>& getDegrees() { return degrees; }
  void reset() {
    for (auto& e : edges) {
      e.flow = 0;
    }
  }

 private:
  int N;
  int maxDegree;
  int minDegree;
  vector<vector<int>> vt;
  vector<int> degrees;
  vector<Edge> edges;
};
class MaxFlow {
 public:
  int dinic(Graph& g, int _s, int _t) {
    auto& nodes = g.getVT();
    N = nodes.size();
    nxt.clear();
    nxt.resize(N, 0);
    s = _s;
    t = _t;
    auto& edges = g.getEdges();
    int maxFlow = 0;
    int flow = 0;
    while (bfs(nodes, edges)) {
      fill(nxt.begin(), nxt.end(), 0);
      while ((flow = dfs(s, nodes, edges, INT_MAX)) != 0) {
        maxFlow += flow;
        fill(nxt.begin(), nxt.end(), 0);
      }
    }
    return maxFlow;
  }
  int EdmondsKarp(Graph& g, int _s, int _t) {
    auto& nodes = g.getVT();
    auto& edges = g.getEdges();
    N = nodes.size();
    s = _s;
    t = _t;
    int maxFlow = 0;
    parents.clear();
    parents.resize(N, make_pair(-1, -1));
    while (bfs2(nodes, edges)) {
      int v = t;
      int flow = INT_MAX;
      while (v != s) {
        int p = parents[v].first;
        auto& e = edges[parents[v].second];
        flow = min(flow, e.cap - e.flow);
        v = p;
      }
      assert(flow > 0);
      maxFlow += flow;
      v = t;
      while (v != s) {
        int p = parents[v].first;
        int idx = parents[v].second;
        edges[idx].flow += flow;
        edges[idx ^ 1].flow -= flow;
        v = p;
      }
    }
    return maxFlow;
  }

 private:
  vector<int> dis;
  vector<int> nxt;
  vector<pair<int, int>> parents;
  int N;
  int s;
  int t;
  bool bfs(vector<vector<int>>& graph, const vector<Edge>& edges) {
    dis.clear();
    dis.resize(N, INT_MAX);
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      auto u = q.front();
      q.pop();
      if (u == t) {
        break;
      }
      for (auto idx : graph[u]) {
        auto& e = edges[idx];
        int v = e.to;
        if (e.cap == e.flow) {
          continue;
        }
        if (dis[v] > dis[u] + 1) {
          dis[v] = dis[u] + 1;
          q.push(v);
        }
      }
    }
    return dis[t] != INT_MAX;
  }
  int dfs(int u, vector<vector<int>>& graph, vector<Edge>& edges, int mx) {
    if (u == t) {
      return mx;
    }
    if (mx == 0) {
      return mx;
    }
    int sum = 0;
    while (nxt[u] < graph[u].size()) {
      int i = graph[u][nxt[u]++];
      auto& e = edges[i];
      int v = e.to;
      int rem = e.cap - e.flow;
      if (rem <= 0 || dis[v] != dis[u] + 1) {
        continue;
      }
      int flow = dfs(v, graph, edges, min(mx - sum, rem));
      if (flow > 0) {
        e.flow += flow;
        edges[i ^ 1].flow -= flow;
        sum += flow;
      }
      if (sum == mx) {
        break;
      }
    }
    return sum;
  }
  bool bfs2(vector<vector<int>>& graph, const vector<Edge>& edges) {
    queue<int> q;
    q.push(s);
    fill(parents.begin(), parents.end(), make_pair(-1, -1));
    while (!q.empty()) {
      auto u = q.front();
      q.pop();
      if (u == t) {
        break;
      }
      for (auto i : graph[u]) {
        auto& e = edges[i];
        int v = e.to;
        if (e.cap == e.flow) {
          continue;
        }
        if (parents[v].first == -1 && v != s) {
          parents[v].first = u;
          parents[v].second = i;
          q.push(v);
        }
      }
    }
    return parents[t].first != -1;
  }
};
class Solution {
 public:
  vector<vector<int>> query(int n1, int n2, vector<pair<int, int>>& edges) {
    Graph graph(n1 + n2);
    int m = edges.size();
    for (int i = 0; i < m; ++i) {
      auto& p = edges[i];
      int u = p.first;
      int v = p.second;
      v += n1;
      graph.addEdge(u, v, 1, i + 1);
    }
    int s = n1 + n2;
    int t = s + 1;
    auto degrees = graph.getDegrees();
    int minDegree = INT_MAX;
    for (int i = 0; i < s; ++i) {
      minDegree = min(minDegree, degrees[i]);
    }
    for (int i = 0; i < n1; ++i) {
      graph.addEdge(s, i, degrees[i] - minDegree, -1);
    }
    for (int i = 0; i < n2; ++i) {
      graph.addEdge(i + n1, t, degrees[i + n1] - minDegree, -2);
    }
    vector<vector<int>> res(minDegree + 1);
    int k = minDegree;
    MaxFlow mf;
    while (k > 0) {
      mf.EdmondsKarp(graph, s, t);
      res[k] = graph.getNotFullEdges();
      if (k > 1) {
        auto& nis = graph.getEdgesIncidentTo(s);
        for (auto idx : nis) {
          graph.extendEdge(idx, 1);
        }
        auto& nit = graph.getEdgesIncidentTo(t);
        for (auto idx : nit) {
          graph.extendEdge(idx ^ 1, 1);
        }
      }
      --k;
    }
    return res;
  }
};
int main(int argc, char** argv) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n1, n2, m;
  cin >> n1 >> n2 >> m;
  vector<pair<int, int>> edges;
  edges.reserve(m);
  for (int i = 0, u = 0, v = 0; i < m; ++i) {
    cin >> u >> v;
    edges.emplace_back(u - 1, v - 1);
  }
  Solution sol;
  auto res = sol.query(n1, n2, edges);
  for (auto& r : res) {
    cout << r.size();
    for (auto i : r) {
      cout << " " << i;
    }
    cout << endl;
  }
  return 0;
}