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.IOException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Scanner;
/*
1 2 4
1 1
1 1
1 2
1 2
 */
public class f {
	public static void main(String[] args) throws IOException, NoSuchFieldException, SecurityException {
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n1 = in.nextInt(), n2 = in.nextInt(), m = in.nextInt();
		int minDeg = 2000;
		int[] deg1 = new int[n1];
		int[] deg2 = new int[n2];
		ArrayList<Edge> es = new ArrayList<>();
		Dinic g = new Dinic(n1+n2);
		for(int i=0;i<m;i++) {
			int u = in.nextInt()-1, v = in.nextInt()-1;
			deg1[u]++;
			deg2[v]++;
			Edge e = g.add(u, v+n1, 1, 0);
			e.id = e.rev.id = i;
		}
		for(int i=0;i<n1;i++) {
			Edge e = g.add(g.s, i, 0, 0);
			es.add(e);
		}
		for(int i=0;i<n2;i++) {
			Edge e = g.add(i+n1, g.t, 0, 0);
			es.add(e);
		}
		for(int a=0;a<n1;a++)
			minDeg = Math.min(deg1[a], minDeg);
		for(int a=0;a<n2;a++)
			minDeg = Math.min(deg2[a], minDeg);
		int flow = 0;
		for(int k=0;k<=minDeg;k++) {
			flow += g.flow(); // k*(n1+n2)-flow
			ArrayList<Integer> ans = new ArrayList<>();
			for(int u=0;u<n1;u++) {
				extract(g, k, u, ans, ans, false);
			}
			for(int v=0;v<n2;v++) {
				extract(g, k, v+n1, new ArrayList<>(), ans, true);
			}
			out.print(ans.size());
			for(int v : ans) {
				out.print(" " + (v+1));
			}
			out.println();
			for(Edge e : es) {
				e.cap++;
			}
		}
		out.close();
		
		
	}

	static void extract(Dinic g, int k, int u, ArrayList<Integer> flowEdges, ArrayList<Integer> greedyEdges, boolean flip) {
		int need = k;
		for (Edge e : g.adj[u]) {
			if (e.v2 == g.s || e.v2 == g.t)
				continue;
			if (e.flow == e.cap ^ flip) {
				flowEdges.add(e.id);
				need--;
			}
		}
		for (Edge e : g.adj[u]) {
			if (e.v2 == g.s || e.v2 == g.t)
				continue;
			if ((e.flow != e.cap ^ flip) && need > 0) {
				greedyEdges.add(e.id);
				need--;
			}
		}
	}

	static class Edge {
		int v1, v2, cap, flow;
		Edge rev;
		int id;

		Edge(int V1, int V2, int Cap, int Flow) {
			v1 = V1;
			v2 = V2;
			cap = Cap;
			flow = Flow;
		}
	}

	static class Dinic {

		ArrayDeque<Integer> q;
		ArrayList<Edge>[] adj;
		int n, s, t, oo = (int) 1E9;
		boolean[] blocked;
		int[] dist;

		public Dinic(int N) {
			n = N;
			s = n++;
			t = n++;
			blocked = new boolean[n];
			dist = new int[n];
			q = new ArrayDeque<Integer>();
			adj = new ArrayList[n];
			for (int i = 0; i < n; ++i)
				adj[i] = new ArrayList<Edge>();
		}

		// Specifying flow can represent minimum flow for circulation.
		Edge add(int v1, int v2, int cap, int flow) {
			Edge e = new Edge(v1, v2, cap, flow);
			Edge rev = new Edge(v2, v1, 0, 0);
			adj[v1].add(rev.rev = e);
			adj[v2].add(e.rev = rev);
			return e;
		}

		boolean bfs() {
			q.clear();
			Arrays.fill(dist, -1);
			dist[t] = 0;
			q.add(t);

			while (!q.isEmpty()) {
				int node = q.poll();
				if (node == s)
					return true;
				for (Edge e : adj[node]) {
					if (e.rev.cap > e.rev.flow && dist[e.v2] == -1) {
						dist[e.v2] = dist[node] + 1;
						q.add(e.v2);
					}
				}
			}
			return dist[s] != -1;
		}

		int dfs(int pos, int min) {
			if (pos == t)
				return min;
			int flow = 0;
			for (Edge e : adj[pos]) {
				int cur = 0;
				if (!blocked[e.v2] && dist[e.v2] == dist[pos] - 1 && e.cap - e.flow > 0) {
					cur = dfs(e.v2, Math.min(min - flow, e.cap - e.flow));
					e.flow += cur;
					e.rev.flow = -e.flow;
					flow += cur;
				}
				if (flow == min)
					return flow;
			}
			blocked[pos] = flow != min;
			return flow;
		}

		int flow() {
			int ret = 0;
			while (bfs()) {
				Arrays.fill(blocked, false);
				ret += dfs(s, oo);
			}
			return ret;
		}

		/*
		 * Vertex cover on bipartite graph (L, R): Find nodes in S side of S/T
		 * min cut (bfs(); dist[i] == -1) L1 = L & S, L2 = L - S, R1 = R & S, R2
		 * = R - S Let B be the set of vertices in R2 that have neighbors in L1
		 * C = L2 | R1 | B Maximum independent set is the complement nodes
		 */
		// #
		ArrayList<Integer> vertexCover() {
			BitSet leftNodes = new BitSet();
			BitSet rightNodes = new BitSet();
			BitSet minCut = new BitSet();
			for (Edge e : adj[s])
				if (e.v1 == s)
					leftNodes.set(e.v2);
			for (Edge e : adj[t])
				if (e.v1 == t)
					rightNodes.set(e.v2);
			bfs();
			for (int i = 0; i < s; ++i)
				if (dist[i] == -1)
					minCut.set(i);

			BitSet l1 = new BitSet();
			l1.or(leftNodes);
			l1.and(minCut);
			BitSet l2 = new BitSet();
			l2.or(leftNodes);
			l2.andNot(minCut);
			BitSet r1 = new BitSet();
			r1.or(rightNodes);
			r1.and(minCut);
			BitSet r2 = new BitSet();
			r2.or(rightNodes);
			r2.andNot(minCut);

			BitSet b = new BitSet();
			for (int bit = r2.nextSetBit(0); bit >= 0; bit = r2.nextSetBit(bit + 1)) {
				for (Edge e : adj[bit]) {
					if (e.v1 == bit && l1.get(e.v2)) {
						b.set(bit);
						break;
					}
				}
			}

			BitSet c = new BitSet();
			c.or(l2);
			c.or(r1);
			c.or(b);
			ArrayList<Integer> ret = new ArrayList<Integer>();
			for (int bit = c.nextSetBit(0); bit >= 0; bit = c.nextSetBit(bit + 1))
				ret.add(bit);
			return ret;
		}// $
	}
}