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 PYTHON3):

Solution:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def FordFulkerson(S,T): #sからFord-Fulkerson
    global lines
    global cost
    global ans

    queue = deque()     #BFS用のdeque
    queue.append([S,INF])
    ed = [True]*N    #到達済み
    ed[S] = False
    route = [0 for i in range(N)]   #ルート
    route[S] = -1

    #BFS
    while queue:
        s,flow = queue.pop()
        for t in lines[s]:  #s->t
            if ed[t]:
                flow = min(cost[s][t],flow)  #flow = min(直前のflow,line容量)
                route[t] = s
                queue.append([t,flow])
                ed[t] = False
                if t == T: #ゴール到達
                    ans += flow
                    break
        else:
            continue
        break
    else:
        return False

    #ラインの更新
    t = T
    s = route[t]
    while s != -1:
        #s->tのコスト減少，ゼロになるなら辺を削除
        cost[s][t] -= flow
        if cost[s][t] == 0:
            lines[s].remove(t)

        #t->s(逆順)のコスト増加，元がゼロなら辺を作成
        if cost[t][s] == 0:
            lines[t].add(s)
        cost[t][s] += flow

        t = s
        s = route[t]
    return True

def PrimeFactoring(x):
    p = 2
    primes = []
    while x >= 2:
        if x%p == 0:
            primes.append(p)
            x //= p
            p = 2
        else:
            p += 1
    return primes

while True:
    X,Y,M = inpl()
    lines = defaultdict(set)
    N = X+Y+2
    S = X+Y
    T = X+Y+1
    cost = [[0]*N for _ in range(N)]

    for i in range(M):
        x,y = inpl()
        lines[x].add(y+X)
        cost[x][y+X] = 1
        
    for i in range(X):
        lines[S].add(i)
        cost[S][i] = 1
    for i in range(Y):
        lines[i+X].add(T)
        cost[i+X][T] = 1

    ans = 0

    while FordFulkerson(S,T):
        pass

    print(ans)

    break