Problem: A bipartite graph G = (V, E) is a graph in which the vertex set V can be divided into two disjoint subsets X and Y such that every edge e ∈ E has one end point in X and the other end point in Y.

A matching M is a subset of edges such that each node in V appears in at most one edge in M.

Given a bipartite graph, find the size of the matching which has the largest size.

Constraints

* 1 ≤ |X|, |Y| ≤ 100
* 0 ≤ |E| ≤ 10,000

Input


|X| |Y| |E|
x0 y0
x1 y1
:
x|E|-1 y|E|-1


|X| and |Y| are the number of vertices in X and Y respectively, and |E| is the number of edges in the graph G. The vertices in X are named with the numbers 0, 1,..., |X|-1, and vertices in Y are named with the numbers 0, 1,..., |Y|-1, respectively.

xi and yi are the node numbers from X and Y respectevely which represent the end-points of the i-th edge.

Output

Print the largest size of the matching.

Example

Input

3 4 6
0 0
0 2
0 3
1 1
2 1
2 3


Output

3

Solution (in JAVA):

Solution:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static class Dinic {

        final ResidualNetwork residualG;
        final int srcVert;
        final int termVert;
        int[] level;
        int[] iter;

        public Dinic(WeightedDigraph graph, int srcVert, int termVert) {
            this.residualG = new ResidualNetwork(graph);
            this.srcVert = srcVert;
            this.termVert = termVert;
        }

        public int computeMaxFlow() {
            level = new int[residualG.numVertex];
            iter = new int[residualG.numVertex];
            int maxFlow = 0;
            for (;;) {
                bfs();
                if (level[termVert] < 0) {
                    return maxFlow;
                }
                Arrays.fill(iter, 0);
                int flow = 0;
                while ((flow = dfs(srcVert, termVert, Integer.MAX_VALUE)) > 0) {
                    maxFlow += flow;
                }
            }
        }

        private void bfs() {
            Arrays.fill(level, -1);
            Queue<Integer> queue = new LinkedList<Integer>();
            level[srcVert] = 0;
            queue.add(srcVert);
            while (!queue.isEmpty()) {
                int v = queue.remove();
                for (WeightedDigraph.Edge edge : residualG.srcEdges[v]) {
                    if (edge.weight > 0 && level[edge.targetVertex] < 0) {
                        level[edge.targetVertex] = level[v] + 1;
                        queue.add(edge.targetVertex);
                    }
                }
            }
        }

        private int dfs(int v, int t, int flow) {
            if (v == t) {
                return flow;
            }
            for (WeightedDigraph.Edge edge : residualG.srcEdges[v]) {
                if (edge.weight > 0 && level[v] < level[edge.targetVertex]) {
                    int minFlow = dfs(edge.targetVertex, t, Math.min(flow, edge.weight));
                    if (minFlow > 0) {
                        edge.weight -= minFlow;
                        residualG.edgeMap.get(edge).weight += minFlow;
                        return minFlow;
                    }
                }
            }
            return 0;
        }
    }

    public static class ResidualNetwork extends WeightedDigraph {

        HashMap<Edge, Edge> edgeMap;

        public ResidualNetwork(WeightedDigraph graph) {
            super(graph.numVertex);
            edgeMap = new HashMap<Edge, Edge>();
            for (int i = 0; i < graph.numVertex; i++) {
                for (WeightedDigraph.Edge edge : graph.srcEdges[i]) {
                    this.addEdge(edge.srcVertex, edge.targetVertex, edge.weight);
                }
            }
        }

        @Override
        public void addEdge(int srcVertex, int targetVertex, int weight) {
            Edge e = new WeightedDigraph.Edge(srcVertex, targetVertex, weight);
            srcEdges[srcVertex].add(e);
            Edge backE = new WeightedDigraph.Edge(targetVertex, srcVertex, 0);
            srcEdges[targetVertex].add(backE);
            edgeMap.put(e, backE);
            edgeMap.put(backE, e);
        }
    }

    public static class WeightedDigraph {

        int numVertex;
        List<Edge>[] srcEdges;

        @SuppressWarnings("unchecked")
        public WeightedDigraph(int numV) {
            this.numVertex = numV;
            srcEdges = new List[numV];

            for (int i = 0; i < numV; i++) {
                srcEdges[i] = new ArrayList<Edge>();
            }
        }

        public void addEdge(int srcVertex, int targetVertex, int weight) {
            Edge e = new WeightedDigraph.Edge(srcVertex, targetVertex, weight);
            srcEdges[srcVertex].add(e);
        }

        public static class Edge {

            int srcVertex;
            int targetVertex;
            int weight;

            public Edge(int srcVertex, int targetVertex, int weight) {
                this.srcVertex = srcVertex;
                this.targetVertex = targetVertex;
                this.weight = weight;
            }

            @Override
            public int hashCode() {
                int hash = 3;
                hash = 59 * hash + this.srcVertex;
                hash = 59 * hash + this.targetVertex;
                return hash;
            }

            @Override
            public boolean equals(Object obj) {
                if (this == obj) {
                    return true;
                }
                if (obj == null) {
                    return false;
                }
                if (getClass() != obj.getClass()) {
                    return false;
                }
                final Edge other = (Edge) obj;
                if (this.srcVertex != other.srcVertex) {
                    return false;
                }
                if (this.targetVertex != other.targetVertex) {
                    return false;
                }
                return true;
            }

        }

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numVertex1 = scanner.nextInt();
        int numVertex2 = scanner.nextInt();
        int numEdge = scanner.nextInt();
        WeightedDigraph graph = new WeightedDigraph(numVertex1 + numVertex2 + 2);
        int srcVert = numVertex1 + numVertex2;
        int termVert = srcVert + 1;
        while (numEdge-- > 0) {
            int v1 = scanner.nextInt();
            int v2 = scanner.nextInt() + numVertex1;
            graph.addEdge(v1, v2, 1);
        }
        for (int vert = 0; vert < numVertex1; vert++) {
            graph.addEdge(srcVert, vert, 1);
        }
        for (int vert = numVertex1; vert < numVertex1 + numVertex2; vert++) {
            graph.addEdge(vert, termVert, 1);
        }
        Dinic maxFlow = new Dinic(graph, srcVert, termVert);
        System.out.println(maxFlow.computeMaxFlow());
    }

}