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 JAVA):

Solution:
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF976F extends PrintWriter {
	CF976F() { super(System.out); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF976F o = new CF976F(); o.main(); o.flush();
	}

	int[] oo, oh; int __ = 1;
	int link(int o, int h) {
		oo[__] = o; oh[__] = h;
		return __++;
	}
	int[] ij, cc; int m_;
	int[] ae, dd; int n_;
	int[] qu;
	void init() {
		oo = new int[1 + m_ * 2]; oh = new int[1 + m_ * 2];
		ij = new int[m_]; cc = new int[m_ * 2]; m_ = 0;
		ae = new int[n_]; dd = new int[n_];
		qu = new int[n_];
	}
	void link_(int i, int j, int c) {
		int h = m_++;
		ij[h] = i ^ j;
		cc[h << 1] = c;
		ae[i] = link(ae[i], h << 1);
		ae[j] = link(ae[j], h << 1 | 1);
	}
	boolean bfs() {
		Arrays.fill(dd, n_);
		int head = 0, cnt = 0;
		dd[0] = 0; qu[head + cnt++] = 0;
		while (cnt > 0) {
			int i = qu[head++]; cnt--;
			int d = dd[i] + 1;
			for (int o = ae[i]; o != 0; o = oo[o]) {
				int h_ = oh[o];
				if (cc[h_] > 0) {
					int h = h_ >> 1;
					int j = i ^ ij[h];
					if (dd[j] > d) {
						dd[j] = d;
						if (j == n_ - 1)
							return true;
						qu[head + cnt++] = j;
					}
				}
			}
		}
		return false;
	}
	boolean dfs(int i) {
		if (i == n_ - 1)
			return true;
		int d = dd[i] + 1;
		for (int o = ae[i]; o != 0; o = oo[o]) {
			int h_ = oh[o];
			if (cc[h_] > 0) {
				int h = h_ >> 1;
				int j = i ^ ij[h];
				if (dd[j] == d && dfs(j)) {
					cc[h_]--; cc[h_ ^ 1]++;
					return true;
				}
			}
		}
		dd[i] = n_;
		return false;
	}
	void dinic() {
		while (bfs())
			while (dfs(0))
				;
	}
	void main() {
		int n1 = sc.nextInt();
		int n2 = sc.nextInt();
		int m = sc.nextInt();
		n_ = 1 + n1 + n2 + 1;
		m_ = n1 + m + n2;
		init();
		int[] d1 = new int[n1 + 1];
		int[] d2 = new int[n2 + 1];
		for (int h = 0; h < m; h++) {
			int i = sc.nextInt();
			int j = sc.nextInt();
			link_(i, n1 + j, 1);
			d1[i]++;
			d2[j]++;
		}
		int d = m;
		for (int i = 1; i <= n1; i++)
			d = Math.min(d, d1[i]);
		for (int i = 1; i <= n2; i++)
			d = Math.min(d, d2[i]);
		for (int i = 1; i <= n1; i++)
			link_(0, i, d1[i] - d);
		for (int i = 1; i <= n2; i++)
			link_(n1 + i, n_ - 1, d2[i] - d);
		int[][] ee = new int[d + 1][m];
		int[] cnt = new int[d + 1];
		for (int k = d; k >= 0; k--) {
			dinic();
			for (int h = 0; h < m; h++)
				if (cc[h << 1] == 1)
					ee[k][cnt[k]++] = h + 1;
			for (int h = m; h < m + n1 + n2; h++)
				cc[h << 1]++;
		}
		for (int k = 0; k <= d; k++) {
			print(cnt[k]);
			for (int h = 0; h < cnt[k]; h++)
				print(" " + ee[k][h]);
			println();
		}
	}
}