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.util.*;
import java.util.stream.*;
import java.util.function.*;
import java.io.*;
import java.math.*;
import java.awt.geom.*;
import static java.util.Comparator.*;
public class Main {
  public static final PrintWriter outWriter = new PrintWriter(System.out);
  public static final int _BUFFER_SIZE = 1 << 16;
  public static final DataInputStream _din = new DataInputStream(System.in);
  public static final byte[] _buffer = new byte[_BUFFER_SIZE];
  public static int _bufferPointer = 0, _bytesRead = 0;
  public static class Node {
    public int row;
    public int col;
    public int row() { return row; }
    public int col() { return col; }
    Node(int row_, int col_) { row=row_; col=col_; }
    int nIn = 0, nOut = 0;
    int level = -1, currNdx = 0;
    HashMap<Node,EdgeI> adj = new HashMap<Node,EdgeI>();
    void addEdge(Node to, int ndx) {
      EdgeI e = adj.get(to);
      if (e == null) {
        e = new Edge(this, to, 0, 0);
        this.adj.put(to, e);
        to.adj.put(this, new RevEdge(e));
      }
      e.ndxes().add(ndx);
      e.addCapacity(1);
      this.nOut++;
      to.nIn++;
    }
    void clear() { level = -1; }
    public int hashCode() { return Objects.hash(row,col); }
    public String toString() { return row+","+col; }
  }
  public static interface EdgeI extends Comparable<EdgeI> {
    public long flow();
    public long capacity();
    public void addFlow(long flow);
    public void addCapacity(long cap);
    public void setCapacity(long cap);
    public Node from();
    public Node to();
    public ArrayList<Integer> ndxes();
    public default long avail() { return capacity() - flow(); }
    public default int compareTo(EdgeI o) { return Long.compare(o.avail(), avail()); }
    public default boolean saturated() { return avail() == 0; }
    public default String s() { return String.format("a%s_%s -> a%s_%s [label=\"%s/%s\"]",from(),from().level,to(),to().level,flow(),capacity()).replaceAll(",","").replaceAll("-1","_"); }
  }
  public static class Edge implements EdgeI {
    public Node from;
    public Node to;
    public long flow;
    public long capacity;
    public Node from() { return from; }
    public Node to() { return to; }
    public long flow() { return flow; }
    public long capacity() { return capacity; }
    Edge(Node from_, Node to_, long flow_, long capacity_) { from=from_; to=to_; flow=flow_; capacity=capacity_; }
    public ArrayList<Integer> ndxes = new ArrayList<Integer>();
    public void addFlow(long f) { flow += f; }
    public void addCapacity(long cap) { capacity += cap; }
    public void setCapacity(long cap) { capacity = cap; }
    public ArrayList<Integer> ndxes() { return ndxes; }
    public String toString() { return s(); }
  }
  public static class RevEdge implements EdgeI {
    public EdgeI base;
    public EdgeI base() { return base; }
    RevEdge(EdgeI base_) { base=base_; }
    public long flow() { return base.capacity()-base.flow(); }
    public long capacity() { return base.capacity(); }
    public Node from() { return base.to(); }
    public Node to() { return base.from(); }
    public ArrayList<Integer> ndxes() { return base.ndxes(); }
    public void addFlow(long f) { base.addFlow(-f); }
    public void addCapacity(long cap) { base.addCapacity(cap); base.addFlow(cap); }
    public void setCapacity(long cap) { base.setCapacity(cap); }
    public String toString() { return s(); }
  }
  public static long maxFlow(Node start, Node end) {
    long out = 0, toAdd;
    while (bfs(start,end)) {
      while ((toAdd = dfs(start,end,Long.MAX_VALUE)) != 0) {
        out += toAdd;
      }
    }
    return out;
  }
  public static Node[] as_ = null, bs_ = null;
  public static Node source_ = null, sink_ = null;
  public static void clearGraph() {
    source_.clear();
    sink_.clear();
    for (Node n : as_) { n.clear(); }
    for (Node n : bs_) { n.clear(); }
  }
  public static boolean bfs(Node start, Node end) {
    clearGraph();
    start.level = 0;
    ArrayDeque<Node> q = new ArrayDeque<Node>();
    q.add(start);
    while (q.size() > 0) {
      Node curr = q.removeFirst();
      if (curr == end) { return true; }
      for (EdgeI e : curr.adj.values()) {
        Node next = e.to();
        if (next.level == -1 && !e.saturated()) {
          next.level = curr.level + 1;
          q.add(next);
        }
      }
    }
    return false;
  }
  public static long dfs(Node start, Node end, long bottleneck) {
    if (start == end) { return bottleneck; }
    if (bottleneck == 0) { return 0; }
    long out = 0;
    for (EdgeI e : start.adj.values()) {
      if (!e.saturated() && e.to().level == start.level+1) {
        long tmp = dfs(e.to(), end, Math.min(bottleneck-out, e.avail()));
        if (tmp != 0) {
          e.addFlow(tmp);
          out += tmp;
        }
      }
    }
    return out;
  }
  public static FileWriter w = null;
  public static void pNode(Node n) throws IOException{
    for (EdgeI e : n.adj.values()) {
      if (e instanceof Edge)
      w.write(e.s()+"\n");
    }
  }
  public static void pGraph() {
    try {
    if (w == null) { w = new FileWriter("/tmp/asdf.dot"); }
    w.write("digraph {\n");
    pNode(source_);
    for (Node n : as_) { pNode(n); }
    for (Node n : bs_) { pNode(n); }
    pNode(sink_);
    w.write("}\n");
    w.flush();
    } catch (Exception e) {}
  }
  public static void main() {
    int n1 = nextInt(), n2 = nextInt(), m = nextInt();
    Node[] as = new Node[n1];
    for (int i = 0; i < as.length; i++) {
      as[i] = new Node(1, i);
    }
    Node[] bs = new Node[n2];
    for (int i = 0; i < bs.length; i++) {
      bs[i] = new Node(2, i);
    }
    for (int i = 0; i < m; i++) {
      Node a = as[nextInt()-1], b = bs[nextInt()-1];
      a.addEdge(b, i+1);
    }
    int minK = Integer.MAX_VALUE;
    Node source = new Node(0, 0), sink = new Node(3, 0);
    for (Node tmp : as) {
      minK = Math.min(minK,tmp.nOut);
      source.addEdge(tmp, -1);
    }
    for (Node tmp : bs) {
      minK = Math.min(minK,tmp.nIn);
      tmp.addEdge(sink, -1);
    }
    as_ = as; bs_ = bs; source_ = source; sink_ = sink;
    String[] out = new String[minK+1];
    for (int i = minK; i >= 0; i--) {
      for (EdgeI e : source.adj.values()) { e.setCapacity(e.to().nOut - i); }
      for (EdgeI e : sink.adj.values()) { e.setCapacity(e.to().nIn - i); }
      maxFlow(source, sink);
      long count = 0;
      StringJoiner join = new StringJoiner(" ");
      for (Node a : as) {
        for (EdgeI e : a.adj.values()) {
          if (e.to().row == 2) {
            long tmp = e.avail();
            count+=tmp;
            for (int j = 0; j < tmp; j++) {
              join.add(e.ndxes().get(j)+"");
            }
          }
        }
      }
      out[i] = count+" "+join;
    }
    for (String s : out) {
      outWriter.println(s);
    }
  }
  public static void main(String[] args) { main(); outWriter.flush(); }
  public static void _fillBuffer() {
    try {
      _bytesRead = _din.read(_buffer, _bufferPointer = 0, _buffer.length);
      if (_bytesRead == -1)
        _buffer[0] = -1;
    } catch (IOException e) {
      throw new UncheckedIOException(e);
    }
  }
  public static byte _read() {
    if (_bufferPointer == _bytesRead)
      _fillBuffer();
    return _buffer[_bufferPointer++];
  }
  public static String next() {
    byte[] strBuf = new byte[64];
    int cnt = 0, c;
    while ((c = _read()) != -1) {
      if (Character.isWhitespace(c)) {
        if (cnt == 0) {
          continue;
        } else {
          break;
        }
      }
      if (strBuf.length == cnt) {
        strBuf = Arrays.copyOf(strBuf, strBuf.length*2);
      }
      strBuf[cnt++] = (byte) c;
    }
    return new String(strBuf, 0, cnt);
  }
  public static String nextLine() {
    byte[] strBuf = new byte[64];
    int cnt = 0, c;
    while ((c = _read()) != -1) {
      if (c == '\n') {
        if (cnt == 0) {
          continue;
        } else {
          break;
        }
      }
      if (strBuf.length == cnt) {
        strBuf = Arrays.copyOf(strBuf, strBuf.length*2);
      }
      strBuf[cnt++] = (byte) c;
    }
    return new String(strBuf, 0, cnt);
  }
  public static int nextInt() {
    int ret = 0;
    byte c = _read();
    while (c <= ' ')
      c = _read();
    boolean neg = (c == '-');
    if (neg)
      c = _read();
    do {
      ret = ret * 10 + c - '0';
    } while ((c = _read()) >= '0' && c <= '9');
    if (neg)
      return -ret;
    return ret;
  }
  public static long nextLong() {
    long ret = 0;
    byte c = _read();
    while (c <= ' ')
      c = _read();
    boolean neg = (c == '-');
    if (neg)
      c = _read();
    do {
      ret = ret * 10 + c - '0';
    } while ((c = _read()) >= '0' && c <= '9');
    if (neg)
      return -ret;
    return ret;
  }
  public static double nextDouble() {
    double ret = 0, div = 1;
    byte c = _read();
    while (c <= ' ')
      c = _read();
    boolean neg = (c == '-');
    if (neg)
      c = _read();
    do {
      ret = ret * 10 + c - '0';
    }
    while ((c = _read()) >= '0' && c <= '9');
    if (c == '.') {
      while ((c = _read()) >= '0' && c <= '9') {
        ret += (c - '0') / (div *= 10);
      }
    }
    if (neg)
      return -ret;
    return ret;
  }
}