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;
template <typename T>
void dbg(T a) {}
template <typename T, typename... Arg>
void dbg(T a, Arg... arg) {}
const int maxn = (1e6) + 7;
const int inf = (1e9) + 7;
const long long LLinf = (1e18) + 7;
const long long INF = 1e18;
const long double eps = 1e-9;
const long long mod = 1e9 + 7;
struct Dinic {
  struct Edge {
    int v;
    long long cap;
    int rev_ind;
    int num;
    bool czy;
    Edge(int to, long long capa, int ind, int NUM)
        : v(to), cap(capa), rev_ind(ind) {
      num = NUM;
      if (cap > 0)
        czy = 1;
      else
        czy = 0;
    }
  };
  int n, source, sink;
  vector<int> starte, d;
  vector<vector<Edge> > nei;
  inline bool bfs() {
    d = vector<int>(n + 1, -1);
    d[source] = 0;
    vector<int> q(1, source);
    for (int i = 0; i < q.size(); i++) {
      int v = q[i];
      for (auto w : nei[v])
        if (d[w.v] == -1 && w.cap) {
          q.push_back(w.v);
          d[w.v] = d[v] + 1;
        }
    }
    return d[sink] != -1;
  }
  long long dfs(int v, long long mincap) {
    if (!mincap || v == sink) return mincap;
    long long fp = 0;
    for (int i = starte[v]; i < nei[v].size(); i++) {
      if (!mincap)
        break;
      else
        starte[v] = i;
      Edge& edge = nei[v][i];
      int w = nei[v][i].v;
      if (d[w] == d[v] + 1) {
        long long f = dfs(w, min(mincap, edge.cap));
        mincap -= f;
        fp += f;
        edge.cap -= f;
        nei[edge.v][edge.rev_ind].cap += f;
      }
    }
    return fp;
  }
  Dinic(int n, int source, int sink)
      : n(n), source(source), sink(sink), nei(n + 1) {}
  long long flow() {
    long long maxflow = 0;
    while (bfs()) {
      starte = vector<int>(n + 1, 0);
      maxflow += dfs(source, INF);
    }
    return maxflow;
  }
  void add_edge(int from, int to, long long capacity, int num,
                long long cap2 = 0) {
    Edge e1(to, capacity, ((int)(nei[to]).size()), num),
        e2(from, cap2, ((int)(nei[from]).size()), num);
    nei[from].push_back(e1);
    nei[to].push_back(e2);
  }
  vector<int> find_source_cc() {
    bfs();
    vector<int> ans;
    for (int i = 0; i <= n; i++)
      if (d[i] != -1) ans.push_back(i);
    return ans;
  }
};
vector<pair<int, int> > wek[maxn];
int res;
bool vis[maxn];
int ile[maxn];
int st[maxn];
pair<int, int> para[maxn];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n1, n2, m;
  cin >> n1 >> n2 >> m;
  res = m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    wek[a].push_back({b + n1, i});
    wek[b + n1].push_back({a, i});
    para[i] = {a, b + n1};
    st[a]++;
    st[b + n1]++;
  }
  for (int i = 1; i <= n1 + n2; i++) res = min(res, st[i]);
  for (int i = 0; i <= res; i++) {
    Dinic cur(n1 + n2 + 2, 0, n1 + n2 + 1);
    for (int j = 1; j <= n1; j++) {
      for (auto s : wek[j]) cur.add_edge(j, s.first, 1, s.second);
      cur.add_edge(0, j, i, 0);
    }
    for (int j = n1 + 1; j <= n2 + n1; j++) cur.add_edge(j, n1 + n2 + 1, i, 0);
    cur.flow();
    for (int j = 0; j <= m; j++) vis[j] = 0;
    for (int j = 0; j <= n1 + n2; j++) ile[j] = 0;
    vector<int> V;
    for (int j = 1; j <= n1; j++)
      for (auto s : cur.nei[j])
        if (s.czy == 1 && s.cap == 0) {
          vis[s.num] = 1;
          V.push_back(s.num);
          ile[para[s.num].first]++;
          ile[para[s.num].second]++;
        }
    for (int j = 1; j <= n1 + n2; j++)
      if (ile[j] < i) {
        for (auto s : wek[j]) {
          if (vis[s.second] == 0) {
            vis[s.second] = 1;
            ile[j]++;
            ile[s.first]++;
            V.push_back(s.second);
          }
          if (ile[j] >= i) break;
        }
      }
    cout << ((int)(V).size()) << " ";
    for (auto s : V) cout << s << " ";
    cout << "\n";
  }
  return 0;
}