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;
const int Maxn = 2000, Group = 2;
vector<int> FEP[Maxn * Group + 5];
vector<pair<int, int> > FE;
void FAE(int FFrom, int Fto, int Fweight) {
  FEP[FFrom].push_back(FE.size());
  FE.push_back(make_pair(Fto, Fweight));
  FEP[Fto].push_back(FE.size());
  FE.push_back(make_pair(FFrom, 0));
}
int FlowDis[Maxn * Group + 5];
queue<pair<int, int> > FlowQueue;
int Flow_BFS(int Flow_Startfrom, int Flow_Endat) {
  memset(FlowDis, 0, sizeof(FlowDis));
  FlowDis[Flow_Startfrom] = 1;
  FlowQueue.push(make_pair(Flow_Startfrom, 1));
  while (!FlowQueue.empty()) {
    int FlowNowx = FlowQueue.front().first,
        FlowNowlen = FlowQueue.front().second;
    FlowQueue.pop();
    for (int i = 0; i < FEP[FlowNowx].size(); i++)
      if (FlowDis[FE[FEP[FlowNowx][i]].first] == 0 &&
          FE[FEP[FlowNowx][i]].second)
        FlowQueue.push(make_pair(FE[FEP[FlowNowx][i]].first, FlowNowlen + 1)),
            FlowDis[FE[FEP[FlowNowx][i]].first] = FlowNowlen + 1;
  }
  if (FlowDis[Flow_Endat]) return FlowDis[Flow_Endat];
  return 0;
}
int Flow_DFS(int FlowNowx, int minn, int Flow_Endat, int Flow_Depth) {
  if (FlowNowx == Flow_Endat) return minn;
  if (FlowDis[Flow_Endat] == Flow_Depth) return 0;
  int Flow_DFS_Return = 0;
  for (int i = 0; i < FEP[FlowNowx].size(); i++)
    if (FlowDis[FE[FEP[FlowNowx][i]].first] == FlowDis[FlowNowx] + 1 &&
        FE[FEP[FlowNowx][i]].second) {
      int Flow_DFS_Answer =
          Flow_DFS(FE[FEP[FlowNowx][i]].first,
                   min(minn - Flow_DFS_Return, FE[FEP[FlowNowx][i]].second),
                   Flow_Endat, Flow_Depth + 1);
      if (Flow_DFS_Answer) {
        FE[FEP[FlowNowx][i]].second -= Flow_DFS_Answer;
        FE[FEP[FlowNowx][i] ^ 1].second += Flow_DFS_Answer;
        return Flow_DFS_Answer;
      }
    }
  return Flow_DFS_Return;
}
int Flow_Dinic(int Flow_Startfrom, int Flow_Endat) {
  int Flow_Dinics_Return = 0;
  while (Flow_BFS(Flow_Startfrom, Flow_Endat))
    Flow_Dinics_Return += Flow_DFS(Flow_Startfrom, 1000000007, Flow_Endat, 1);
  return Flow_Dinics_Return;
}
void Flow_init() {
  FE.clear();
  for (int i = 0; i < Maxn * Group + 5; i++) FEP[i].clear();
}
vector<int> ans[4003];
int n1, n2, m, u, v, d[4003], mnn = 233333;
int main() {
  cin >> n1 >> n2 >> m;
  for (int i = 0; i < m; i++) {
    cin >> u >> v;
    d[u]++;
    d[v + n1]++;
    FAE(u, v + n1, 1);
  }
  for (int i = 1; i <= n1 + n2; i++) mnn = min(mnn, d[i]);
  for (int i = 1; i <= n1; i++) FAE(0, i, d[i] - mnn);
  for (int i = n1 + 1; i <= n1 + n2; i++) FAE(i, 4003, d[i] - mnn);
  for (int i = mnn; i >= 0; i--) {
    Flow_Dinic(0, 4003);
    for (int j = 0; j < m * 2; j += 2)
      if (FE[j].first != 4003 && FE[j ^ 1].first && FE[j].second)
        ans[i].push_back(j / 2 + 1);
    for (int j = m * 2; j < FE.size(); j += 2) FE[j].second++;
  }
  for (int i = 0; i <= mnn; i++) {
    cout << ans[i].size();
    for (int j = 0; j < ans[i].size(); j++) cout << ' ' << ans[i][j];
    cout << endl;
  }
}