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.*;
import java.util.*;

public class F implements Runnable{
	public static void main (String[] args) {new Thread(null, new F(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");

		int n1 = fs.nextInt();
		int n2 = fs.nextInt();
		int m = fs.nextInt();
		int nodes = n1 + n2 + 2;
		int src = n1 + n2;
		int snk = src + 1;
		int[] deg = new int[n1 + n2];
		int[] us = new int[m], vs = new int[m];
		MaxFlowDinic mfd = new MaxFlowDinic();
		ArrayList<Edge>[] graph = mfd.createGraph(nodes);
		
		for(int i = 0; i < m; i++) {
			int u = fs.nextInt() - 1;
			int v = fs.nextInt() - 1;
			deg[u]++; deg[v + n1]++;
			us[i] = u; vs[i] = v;
		}
		
		int k = m + 1;
		for(int i = 0; i < deg.length; i++) {
			k = Math.min(k, deg[i]);
		}
		ArrayList<Integer>[] res = new ArrayList[k + 1];
		for(int i = 0; i < res.length; i++) res[i] = new ArrayList<>();
		
		for(int i = 0; i < m; i++) {
			int u = us[i], v = vs[i];
			mfd.addEdge(graph, u, v + n1, 1, i);
		}
		for(int i = 0; i < n1; i++) {
			mfd.addEdge(graph, src, i, deg[i] - k, i);
		}
		for(int i = 0; i < n2; i++) {
			mfd.addEdge(graph, i + n1, snk, deg[i + n1] - k, i);
		}
		
		while(k > 0) {
			int flow = mfd.maxFlow(graph, src, snk);
//			System.out.printf("K = %d Flow = %d\n", k, flow);
			for(int i = 0; i < n1; i++) {
				for(Edge e : graph[i]) {
					if(e.f == 0 && e.cap > 0) {
//						System.out.printf("Edge (%d -> %d) not used.\n", i + 1, e.t - n1 + 1);
						res[k].add(e.id);
					}
				}
			}
			
			for(Edge e : graph[src]) e.cap++;
			for(int i = 0; i < n2; i++) {
				for(Edge e : graph[i + n1]) {
					if(e.t == snk) {
//						System.out.printf("Edge Inc (%d, %d) F = %d C = %d\n", i + n1 + 1, e.t + 1, e.f, e.cap);
						e.cap++;
					}
				}
			}
			k--;
//			System.out.println();
		}
		
		for(int i = 0; i < res.length; i++) {
			out.print(res[i].size());
			for(int j : res[i]) out.print(" " + (j+1));
			out.println();
		}

		out.close();
	}

	class Edge {
		int t, rev, cap, f, id;
		public Edge(int t, int rev, int cap, int i) {
			this.t = t;
			this.rev = rev;
			this.cap = cap;
			id = i;
		}
	}

	class MaxFlowDinic {
		ArrayList<Edge>[] createGraph(int nodes) {
			ArrayList<Edge>[] graph = new ArrayList[nodes];
			for (int i = 0; i < nodes; i++)
				graph[i] = new ArrayList<>();
			return graph;
		}

		void addEdge(List<Edge>[] graph, int s, int t, int cap, int id) {
			graph[s].add(new Edge(t, graph[t].size(), cap, id));
			graph[t].add(new Edge(s, graph[s].size() - 1, 0, id));
		}

		boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) {
			Arrays.fill(dist, -1);
			dist[src] = 0;
			int[] Q = new int[graph.length];
			int sizeQ = 0;
			Q[sizeQ++] = src;
			for (int i = 0; i < sizeQ; i++) {
				int u = Q[i];
				for (Edge e : graph[u]) {
					if (dist[e.t] < 0 && e.f < e.cap) {
						dist[e.t] = dist[u] + 1;
						Q[sizeQ++] = e.t;
					}
				}
			}
			return dist[dest] >= 0;
		}

		int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
			if (u == dest)
				return f;
			for (; ptr[u] < graph[u].size(); ++ptr[u]) {
				Edge e = graph[u].get(ptr[u]);
				if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
					int df = dinicDfs(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
					if (df > 0) {
						e.f += df;
						graph[e.t].get(e.rev).f -= df;
						return df;
					}
				}
			}
			return 0;
		}

		int maxFlow(List<Edge>[] graph, int src, int dest) {
			int flow = 0;
			int[] dist = new int[graph.length];
			while (dinicBfs(graph, src, dest, dist)) {
				int[] ptr = new int[graph.length];
				while (true) {
					int df = dinicDfs(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
					if (df == 0)
						break;
					flow += df;
				}
			}
			return flow;
		}
	}
	
	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}