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:
// Java program for implementation of Ford Fulkerson algorithm
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.LinkedList;

public class Main {
    static int V; //Number of vertices in graph
    public static class FordFulkerson {

        /* Returns true if there is a path from source 's' to sink
        't' in residual graph. Also fills parent[] to store the
        path */
        boolean bfs(int rGraph[][], int s, int t, int parent[]) {
            // Create a visited array and mark all vertices as not
            // visited
            boolean visited[] = new boolean[V];
            for(int i=0; i<V; ++i)
                visited[i]=false;

            // Create a queue, enqueue source vertex and mark
            // source vertex as visited
            LinkedList<Integer> queue = new LinkedList<Integer>();
            queue.add(s);
            visited[s] = true;
            parent[s]=-1;

            // Standard BFS Loop
            while (queue.size()!=0)
            {
                int u = queue.poll();

                for (int v=0; v<V; v++)
                {
                    if (visited[v]==false && rGraph[u][v] > 0)
                    {
                        queue.add(v);
                        parent[v] = u;
                        visited[v] = true; 
                    } 
                } 
            } 

            // If we reached sink in BFS starting from source, then 
            // return true, else false 
            return (visited[t] == true); 
        } 

        // Returns tne maximum flow from s to t in the given graph 
        int fordFulkerson(int graph[][], int s, int t) 
        { 
            int u, v; 

            // Create a residual graph and fill the residual graph 
            // with given capacities in the original graph as 
            // residual capacities in residual graph 

            // Residual graph where rGraph[i][j] indicates 
            // residual capacity of edge from i to j (if there 
            // is an edge. If rGraph[i][j] is 0, then there is 
            // not) 
            int rGraph[][] = new int[V][V]; 

            for (u = 0; u < V; u++) 
                for (v = 0; v < V; v++) 
                    rGraph[u][v] = graph[u][v]; 

            // This array is filled by BFS and to store path 
            int parent[] = new int[V]; 

            int max_flow = 0; // There is no flow initially 

            // Augment the flow while tere is path from source 
            // to sink 
            while (bfs(rGraph, s, t, parent)) 
            { 
                // Find minimum residual capacity of the edhes 
                // along the path filled by BFS. Or we can say 
                // find the maximum flow through the path found. 
                int path_flow = Integer.MAX_VALUE; 
                for (v=t; v!=s; v=parent[v]) 
                { 
                    u = parent[v]; 
                    path_flow = Math.min(path_flow, rGraph[u][v]); 
                } 

                // update residual capacities of the edges and 
                // reverse edges along the path 
                for (v=t; v != s; v=parent[v]) 
                { 
                    u = parent[v]; 
                    rGraph[u][v] -= path_flow; 
                    rGraph[v][u] += path_flow; 
                } 

                // Add path flow to overall flow 
                max_flow += path_flow;
            }

            // Return the overall flow
            return max_flow;
        }
    }
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int X = Integer.parseInt(sc.next());
        int Y = Integer.parseInt(sc.next());
        V = X+Y+2;
        int E = Integer.parseInt(sc.next());
        int[][] graph = new int[V][V];
        for (int i=0;i<E;i++) {
            int x = Integer.parseInt(sc.next())+1;
            int y = X+Integer.parseInt(sc.next())+1;
            graph[x][y] = 1;
            graph[0][x] = 1;
            graph[y][V-1] =1;
        }
        FordFulkerson m = new FordFulkerson();
        System.out.println(m.fordFulkerson(graph, 0, V-1));

    }
}