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;
using pii = pair<int, int>;
template <class T>
struct Dinic {
  struct Edge {
    int u, rev, i;
    T cap;
  };
  static const T MX = numeric_limits<T>::max();
  int n, s, t;
  vector<int> level, idx;
  vector<vector<Edge>> adjList;
  Dinic(int n, int s, int t) : n(n), s(s), t(t), level(n), idx(n), adjList(n){};
  void addEdge(int v, int u, T c, int idx) {
    adjList[v].push_back({u, (int)adjList[u].size(), idx, c});
    adjList[u].push_back({v, (int)adjList[v].size() - 1, idx, 0});
  }
  bool bfs() {
    queue<int> q;
    fill(level.begin(), level.end(), -1);
    q.push(s);
    level[s] = 0;
    while (!q.empty()) {
      int v = q.front();
      q.pop();
      if (v == t) return true;
      for (Edge e : adjList[v]) {
        if (e.cap <= 0 || level[e.u] != -1) continue;
        level[e.u] = level[v] + 1;
        q.push(e.u);
      }
    }
    return false;
  }
  T dfs(int v, T flow) {
    if (v == t) return flow;
    if (flow == 0) return 0;
    T cont = 0;
    for (; idx[v] < adjList[v].size(); idx[v]++) {
      Edge &e = adjList[v][idx[v]];
      if (e.cap <= 0 || level[e.u] <= level[v]) continue;
      T mnFlow = dfs(e.u, min(flow, e.cap));
      if (mnFlow > 0) {
        cont += mnFlow;
        flow -= mnFlow;
        e.cap -= mnFlow;
        adjList[e.u][e.rev].cap += mnFlow;
      }
      if (flow == 0) break;
    }
    return cont;
  }
  T maxFlow() {
    T flow, ans = 0;
    while (bfs()) {
      fill(idx.begin(), idx.end(), 0);
      while ((flow = dfs(s, MX)) > 0) {
        ans += flow;
      }
    }
    return ans;
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n1, n2, m;
  cin >> n1 >> n2 >> m;
  int n = 2 + n1 + n2;
  Dinic<int> g(n, 0, n1 + n2 + 1);
  for (int i = 1; i <= n1; i++) g.addEdge(0, i, 0, -1);
  for (int i = n1 + 1; i <= n1 + n2; i++) g.addEdge(i, n1 + n2 + 1, 0, -1);
  vector<int> deg(n);
  int ai, bi;
  for (int i = 1; i <= m; i++) {
    cin >> ai >> bi;
    g.addEdge(ai, bi + n1, 1, i);
    deg[ai]++;
    deg[n1 + bi]++;
  }
  int mn = *min_element(deg.begin() + 1, deg.end() - 1);
  for (int v = 1; v <= n1; v++) g.adjList[0][v - 1].cap = deg[v] - mn;
  for (int v = n1 + 1; v <= n1 + n2; v++) g.adjList[v][0].cap = deg[v] - mn;
  vector<vector<int>> res(mn + 1);
  for (int d = mn; d >= 0; d--) {
    g.maxFlow();
    for (int v = 1; v <= n1; v++) {
      for (auto [u, rev, i, c] : g.adjList[v]) {
        if (i == -1 || c == 0) continue;
        res[d].emplace_back(i);
      }
    }
    for (int v = 1; v <= n1; v++) {
      g.adjList[0][v - 1].cap++;
    }
    for (int v = n1 + 1; v <= n1 + n2; v++) {
      g.adjList[v][0].cap++;
    }
  }
  for (auto vec : res) {
    cout << vec.size() << ' ';
    for (int x : vec) {
      cout << x << ' ';
    }
    cout << '\n';
  }
  return 0;
}