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;
inline int read() {
  int f = 1, ans = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    ans = ans * 10 + c - '0';
    c = getchar();
  }
  return f * ans;
}
const int MAXN = 1e5 + 11;
struct Edge {
  int u, v, w, id, nex;
} E[MAXN << 1];
int head[MAXN], X, Y, M, cnt, S, T;
void add(int u, int v, int w, int id) {
  E[cnt].u = u, E[cnt].v = v, E[cnt].w = w, E[cnt].id = id,
  E[cnt].nex = head[u], head[u] = cnt++;
  w = 0, swap(u, v);
  E[cnt].u = u, E[cnt].v = v, E[cnt].w = w, E[cnt].id = id,
  E[cnt].nex = head[u], head[u] = cnt++;
  return;
}
queue<int> que;
int dis[MAXN];
bool bfs() {
  memset(dis, 127 / 3, sizeof(dis));
  int inf = dis[0];
  dis[S] = 0;
  que.push(S);
  while (!que.empty()) {
    int xx = que.front();
    que.pop();
    for (int i = head[xx]; i != -1; i = E[i].nex)
      if (E[i].w && dis[E[i].v] > dis[xx] + 1) {
        dis[E[i].v] = dis[xx] + 1;
        que.push(E[i].v);
      }
  }
  return dis[T] != inf;
}
int dfs(int u, int flow) {
  if (u == T) return flow;
  int used = 0;
  for (int i = head[u]; i != -1; i = E[i].nex)
    if (dis[E[i].v] == dis[u] + 1 && E[i].w) {
      int slow = dfs(E[i].v, min(flow - used, E[i].w));
      E[i].w -= slow, E[i ^ 1].w += slow;
      used += slow;
      if (used == flow) break;
    }
  if (!used) dis[u] = -1;
  return used;
}
int d[MAXN], Real;
vector<int> vec[MAXN];
int Dinic() {
  int Ans = 0;
  while (bfs()) Ans += dfs(S, INT_MAX);
  return Ans;
}
int main() {
  memset(head, -1, sizeof(head));
  X = read(), Y = read(), M = read();
  S = 0, T = X + Y + 1;
  for (int i = 1; i <= M; i++) {
    int u = read(), v = read() + X;
    d[u]++, d[v]++;
    add(u, v, 1, i);
  }
  int Minn = INT_MAX;
  for (int i = 1; i <= X + Y; i++) Minn = min(Minn, d[i]);
  for (int i = 1; i <= X; i++) add(S, i, d[i] - Minn, 0);
  for (int i = 1; i <= Y; i++) add(i + X, T, d[i + X] - Minn, 0);
  for (int i = Minn; i >= 0; i--) {
    int p = Dinic();
    for (int j = 0; j < cnt; j++)
      if (E[j].u <= X && E[j].v > X && E[j].w) vec[i].push_back(E[j].id);
    for (int j = 0; j < cnt; j++)
      if (E[j].u == S || E[j].v == T) E[j].w++;
  }
  for (int i = 0; i <= Minn; i++) {
    printf("%ld ", vec[i].size());
    for (auto v : vec[i]) printf("%d ", v);
    printf("\n");
  }
  return 0;
}