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:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class MinimalKcovering {

	public static int n1, n2, m;
	public static int[][] isEdge;
	public static ArrayList<Edge>[] edge; // n1 .. n2 .. s t
	public static ArrayList<Edge>[] edgeB;
	public static int s, t;
	static int[] degree;;
	static int k;
	static int minDeg;
	// static String result = "";
	public static ArrayList<Integer>[] re;

	static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}

	static class Edge {
		public ArrayList<Integer> id;
		public int source;
		public int cap;
		public int flow;
		public int dest;
		public Edge linked;

		public Edge(int id, int source, int des, int flow, int cap) {
			this.id = new ArrayList<Integer>();
			this.id.add(id);
			this.source = source;
			this.dest = des;
			this.cap = cap;
			this.flow = flow;
		}

		public int getResidualCap() {
			return (cap - flow);
		}
	}

	public static ArrayList<Edge> path = new ArrayList<Edge>();

	public static void main(String argv[]) throws IOException {
		BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
		int i, j;
		initData();
		while (k > 0) {
			maxFlow();
			appendListEdge();
			decreasingK();
		}
		for (i = 0; i <= minDeg; i++) {
			log.write(re[i].size() + " ");
			for (j = 0; j < re[i].size(); j++)
				log.write(re[i].get(j) + " ");
			log.write("\n");
		}
		log.flush();
	}

	@SuppressWarnings("unchecked")
	public static void initData() {
		FastScanner sc = new FastScanner(System.in);
		n1 = sc.nextInt();
		n2 = sc.nextInt();
		m = sc.nextInt();
		s = n1 + n2;
		t = s + 1;
		degree = new int[n1 + n2];
		edge = new ArrayList[n1 + n2 + 2];
		edgeB = new ArrayList[n1 + n2 + 2];
		isEdge = new int[n1][n2];
		int i, j, so, de;
		for (i = 0; i < n1 + n2 + 2; i++) {
			edge[i] = new ArrayList<Edge>();
			edgeB[i] = new ArrayList<Edge>();
		}
		for (i = 0; i < m; i++) {
			so = sc.nextInt() - 1;
			de = sc.nextInt() - 1;
			degree[so]++;
			degree[de + n1]++;
			if (isEdge[so][de] == 0) {
				isEdge[so][de] = 1;
				edge[so].add(new Edge(i + 1, so, de + n1, 0, 1));
			} else {
				for (j = 0; j < edge[so].size(); j++) {
					if (edge[so].get(j).dest == de + n1) {
						edge[so].get(j).id.add(i + 1);
						edge[so].get(j).cap++;
					}
				}
			}
		}
		Edge e, e1;
		for (i = 0; i < n1 + n2; i++) {
			for (j = 0; j < edge[i].size(); j++) {
				e = edge[i].get(j);
				e1 = new Edge(-1, e.dest, e.source, e.cap, e.cap);
				e.linked = e1;
				e1.linked = e;
				edgeB[e.dest].add(e1);
			}
		}
		minDeg = degree[0];
		for (i = 1; i < n1 + n2; i++) {
			minDeg = Math.min(minDeg, degree[i]);
		}
		k = minDeg;
		re = new ArrayList[minDeg + 1];
		for (i = 0; i <= minDeg; i++) {
			re[i] = new ArrayList<Integer>();
		}
		for (i = 0; i < n1; i++) {
			edge[s].add(new Edge(0, s, i, 0, degree[i] - k));
		}
		for (i = 0; i < n2; i++) {
			edge[i + n1].add(new Edge(0, i + n1, t, 0, degree[i + n1] - k));
		}
	}

	static ArrayList<Integer> done = new ArrayList<Integer>();
	
	public static boolean dfs(int source) {
		done.add(source);
		if (source == t) {
			return true;
		}
		Edge e;
		for (int i = 0; i < edge[source].size(); i++) {
			e = edge[source].get(i);
			if (!done.contains(e.dest) && e.getResidualCap() > 0 && dfs(e.dest)) {
				path.add(0, e);
				return true;
			}
		}
		for (int i = 0; i < edgeB[source].size(); i++) {
			e = edgeB[source].get(i);
			if (!done.contains(e.dest) && e.getResidualCap() > 0 && dfs(e.dest)) {
				path.add(0, e);
				return true;
			}
		}
		return false;
	}

	public static int getCritical() {
		int min = path.get(0).getResidualCap();
		for (int i = 1; i < path.size(); i++) {
			if (path.get(i).getResidualCap() < min) {
				min = path.get(i).getResidualCap();
			}
		}
		return min;
	}

	public static void maxFlow() {
		int gain, j;
		Edge e;
		while (true) {
			path.clear();
			done.clear();
			if (!dfs(s)) {
				break;
			}
			gain = getCritical();
			for (int i = 0; i < path.size(); i++) {
				e = path.get(i);
				e.flow += gain;
				if (e.source != s && e.dest != t) {
					e.linked.flow -= gain;
				}
			}
		}
	}

	public static void appendListEdge() {
		int i, j, p, res;
		int cur = k;
		for (i = 0; i < n1; i++) {
			for (j = 0; j < edge[i].size(); j++) {
				res = edge[i].get(j).getResidualCap();
				if (res > 0) {
					for (p = 0; p < res; p++) {
						re[cur].add(edge[i].get(j).id.get(p));
					}
				}
			}
		}
	}

	public static void decreasingK() {
		int i;
		k--;
		for (i = 0; i < n1; i++) {
			edge[s].get(i).cap++;
		}
		for (i = 0; i < n2; i++) {
			edge[i + n1].get(0).cap++;
		}
	}
}