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 ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int N = 2005, M = 998244353, INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
void Main();
void debug() { cerr << endl; }
template <typename T, typename... Ts>
void debug(T x, Ts... y) {
  cerr << "\033[31m" << x << "\033[0m";
  if (sizeof...(y) > 0) cerr << ' ';
  debug(y...);
}
template <typename T>
void debug(const T& a, int l, int r, char c) {
  for (int i = l; i <= r; ++i)
    cerr << "\033[31m" << a[i] << "\033[0m" << (i == r ? '\n' : c);
}
void print() { cout << '\n'; }
template <typename T, typename... Ts>
void print(T x, Ts... y) {
  cout << x;
  if (sizeof...(y) > 0) cout << ' ';
  print(y...);
}
template <typename T>
void print(const T& a, int l, int r, char c) {
  for (int i = l; i <= r; ++i) cout << a[i] << (i == r ? '\n' : c);
}
void input() {}
template <typename T, typename... Ts>
void input(T& x, Ts&... y) {
  cin >> x;
  input(y...);
}
template <typename T>
void input(T* a, int l, int r) {
  for (int i = l; i <= r; ++i) cin >> a[i];
}
template <typename T>
void input(vector<T>& a, int l, int r) {
  for (int i = l; i <= r; ++i) cin >> a[i];
}
template <typename T>
void Max(T& a, T b) {
  if (a < b) a = b;
}
template <typename T>
void Min(T& a, T b) {
  if (a > b) a = b;
}
template <typename T>
void Add(T& a, T b) {
  a += b;
  if (a > M) a -= M;
  if (a < 0) a += M;
}
template <typename T>
void Mul(T& a, T b) {
  a = a * b % M;
}
template <typename T>
T Mod(T a) {
  return (a % M + M) % M;
}
int RD() {
  int x;
  cin >> x;
  return x;
}
int main(int argc, char** argv) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  Main();
}
template <typename T, int N, T oo>
struct Dinic {
  int n, s, t;
  struct edge {
    int v;
    T w;
    int rev;
  };
  vector<edge> G[N];
  void add(int u, int v, T w) {
    G[u].push_back({v, w, (int)G[v].size()});
    G[v].push_back({u, 0, (int)G[u].size() - 1});
  }
  void init(int n_) {
    n = n_;
    for (int i = 0; i <= n; i++) G[i].clear();
  }
  int dis[N], cur[N];
  bool bfs() {
    fill(dis, dis + n + 1, -1);
    fill(cur, cur + n + 1, 0);
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (edge& e : G[u])
        if (e.w && dis[e.v] == -1) {
          dis[e.v] = dis[u] + 1;
          q.push(e.v);
        }
    }
    return dis[t] != -1;
  }
  T dfs(int u, T f) {
    if (u == t) return f;
    T used = 0;
    for (int& i = cur[u]; i < (int)G[u].size() && f > used; i++) {
      int v = G[u][i].v;
      T &w = G[u][i].w, &revw = G[v][G[u][i].rev].w;
      if (dis[v] != dis[u] + 1 || w <= 0) continue;
      T t = dfs(v, min(f - used, w));
      used += t;
      w -= t;
      revw += t;
    }
    return used;
  }
  T maxflow(int s_, int t_) {
    s = s_, t = t_;
    T ret = 0;
    while (bfs()) ret += dfs(s, oo);
    return ret;
  }
};
Dinic<int, N << 1, INF> F;
vector<int> ans[N];
int deg[N << 1];
pii E[N];
void Main() {
  int n1, n2, m;
  input(n1, n2, m);
  const int s = n1 + n2 + 1, t = s + 1;
  F.init(t);
  for (int i = 1; i <= m; ++i) {
    int u = RD(), v = RD() + n1;
    ++deg[u];
    ++deg[v];
    F.add(u, v, 1);
    E[i] = {u, F.G[u].size() - 1};
  }
  int k = *min_element(deg + 1, deg + n1 + n2 + 1);
  for (int i = 1; i <= n1; ++i) F.add(s, i, deg[i] - k);
  for (int i = n1 + 1; i <= n1 + n2; ++i) F.add(i, t, deg[i] - k);
  for (int i = k; i >= 0; --i) {
    F.maxflow(s, t);
    for (int j = 1; j <= m; ++j)
      if (F.G[E[j].first][E[j].second].w != 0) ans[i].push_back(j);
    for (auto&& e : F.G[s]) ++e.w;
    for (auto&& e : F.G[t]) ++F.G[e.v][e.rev].w;
  }
  for (int i = 0; i <= k; ++i) {
    cout << ans[i].size() << ' ';
    print(ans[i], 0, (int)ans[i].size() - 1, ' ');
    if (!ans[i].size()) print();
  }
}