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 Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.flush();out.close();
    }
        static class TaskE {
          int MAX,gMAX=Integer.MAX_VALUE;
          int rc[][],cap[][],ex[],H[],S,T;
          boolean inc[];
          class pair{
           int n,id;pair(int a,int b){n=a;id=b;}
          }
          void pr(int it,int n1,int n2){
          ArrayDeque<Integer> ad=new ArrayDeque<>();
          {//init
           rc=new int[MAX][MAX];
           ex=new int[MAX];H=new int[MAX];inc=new boolean[MAX];
           for(int i=1;i<=n1;i++){
            for(pair j:ja[i]){
             rc[i][j.n]+=1;
            }
            //preflow
            ex[i]=it;
            rc[i][0]=it;
            H[0]=n1+n2+2;H[i]=1;inc[i]=true;ad.add(i);
           }
           for(int i=n1+1;i<=n1+n2;i++)rc[i][n1+n2+1]=it;
          }
          
          while(!ad.isEmpty()){
           int u=ad.getFirst(),min=gMAX;
           for(pair v:ja[u]){
            if(ex[u]==0)break;
            if(rc[u][v.n]!=0){
             if(H[v.n]<H[u]){
              int flow=Math.min(rc[u][v.n],ex[u]);
              ex[u]-=flow;ex[v.n]+=flow;
              rc[u][v.n]-=flow;rc[v.n][u]+=flow;
              if(v.n!=S&&v.n!=T&&!inc[v.n]){
               inc[v.n]=true;ad.add(v.n);
              }
             }
             min=Math.min(min,H[v.n]);
            }
           }
           if(ex[u]!=0){
            H[u]=min+1;
           }else{
            ad.pop();inc[u]=false;
           }
          }
         }
          public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n1=in.nextInt(),n2=in.nextInt(),m=in.nextInt();
            MAX=n1+n2+10;
            int it=make(n1,n2,m,in);
            ArrayList<Integer> al=new ArrayList<>();
            out.println(0);
            int cnt[]=new int[MAX];boolean inc[]=new boolean[m+1];
            for(int z=1;z<=it;z++){
             al.clear();
             Arrays.fill(cnt,0);Arrays.fill(inc,false);
             pr(z,n1,n2);
             for(int i=1;i<=n1;i++){
              for(pair j:ja[i]){
               if(cap[i][j.n]-rc[i][j.n]!=0&&j.id!=-1){
                cnt[i]++;cnt[j.n]++;inc[j.id]=true;
                al.add(j.id);rc[i][j.n]++;
               }
              }
             }
             for(int i=1;i<=n1+n2;i++){
              if(cnt[i]>=z)continue;
              int d=z-cnt[i];
              for(pair j:ja[i]){
               if(j.id==-1||inc[j.id])continue;
               al.add(j.id);--d;inc[j.id]=true;
               if(d==0)break;   
              }
             }
             out.print(al.size());
             for(int i=0;i<al.size();i++)out.print(" "+al.get(i));
             out.println();
            }
          }
          pair ja[][];int from[],to[],c[];
              int make(int n1,int n2,int m,InputReader in){
               int tot=n1+n2+2;
               ja=new pair[tot][];from=new int[m];to=new int[m];
               c=new int[tot];
               S=0;T=tot-1;
               cap=new int[MAX][MAX];
               int it=gMAX;
               for(int i=0;i<m;i++){
                from[i]=in.nextInt();to[i]=in.nextInt()+n1;
                c[from[i]]++;c[to[i]]++;
                cap[from[i]][to[i]]++;
               }
               for(int i=1;i<=n1+n2;i++)it=Math.min(it,c[i]);
               c[0]=n1;c[tot-1]=n2;
               for(int i=1;i<=n1+n2;i++)c[i]++;
               for(int i=0;i<=n1+n2+1;i++){
                ja[i]=new pair[c[i]];c[i]=0;
               }
               for(int i=0;i<m;i++){
                ja[from[i]][c[from[i]]++]=new pair(to[i],i+1);
                ja[to[i]][c[to[i]]++]=new pair(from[i],i+1);
               }
               for(int i=1;i<=n1;i++){
                ja[S][c[S]++]=new pair(i,-1);
                ja[i][c[i]]=new pair(S,-1);
               }
               for(int i=n1+1;i<=n1+n2;i++){
                ja[T][c[T]++]=new pair(i,-1);
                ja[i][c[i]]=new pair(T,-1);
               }
               return it;
              }
       }
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

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

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}