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 deque


class Bipartite_Matching:
    """二部グラフの最大マッチングを求めるなどする"""

    def __init__(self, input_graph: list):
        """重み無し二部グラフinput_graphを入力する"""
        n = len(input_graph)
        self.INF = float("inf")
        # DFSでグラフを2色に彩色する
        visited = [-1] * n
        for i in range(n):
            if visited[i] >= 0:
                continue
            visited[i] = 0
            q = deque([i]) 
            while q:
                _from = q.pop()
                for to in input_graph[_from]:
                    if visited[to] >= 0:
                        continue
                    visited[to] = visited[_from] ^ 1
                    q.append(to)

        # 残余グラフを構築する
        self.s = n
        self.t = n + 1
        self.n = n + 2
        self.graph = [[] for i in range(self.n)]
        used = set([])
        for pos1 in range(n):
            if visited[pos1] == 0:
                self.add_edge(self.s, pos1)
            else:
                self.add_edge(pos1, self.t)
            for pos2 in input_graph[pos1]:
                if (min(pos1, pos2), max(pos1, pos2)) in used:
                    continue
                used.add((min(pos1, pos2), max(pos1, pos2)))
                if visited[pos1] == 0:
                    self.add_edge(pos1, pos2)
                else:
                    self.add_edge(pos2, pos1)
 
    def add_edge(self, _from: int, to: int):
        """残余グラフを構築
        1. _fromからtoへ向かう容量capacity = 1の辺をグラフに追加する
        2. toから_fromへ向かう容量0の辺をグラフに追加する
        """
        forward = [to, 1, None]
        forward[2] = backward = [_from, 0, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)
 
    def bfs(self, s: int, t: int):
        """capacityが正の辺のみを通ってsからtに移動可能かどうかBFSで探索
        level: sからの最短路の長さ
        """
        self.level = [-1] * self.n
        q = deque([s])
        self.level[s] = 0
        while q:
            _from = q.popleft()
            for to, capacity, _ in self.graph[_from]:
                if capacity > 0 and self.level[to] < 0:
                    self.level[to] = self.level[_from] + 1
                    q.append(to)
 
    def dfs(self, _from: int, t: int, f: int) -> int:
        """流量が増加するパスをDFSで探索
        BFSによって作られた最短路に従ってfを更新する
        """
        if _from == t:
            return f
        for edge in self.itr[_from]:
            to, capacity, reverse_edge = edge
            if capacity > 0 and self.level[_from] < self.level[to]:
                d = self.dfs(to, t, min(f, capacity))
                if d > 0:
                    edge[1] -= d
                    reverse_edge[1] += d
                    return d
        return 0
 
    def max_flow(self):
        """s-tパス上の最大流を求める = 最大マッチングを求める
        計算量: O(|E||V|^2)
        """
        flow = 0
        while True:
            self.bfs(self.s, self.t)
            if self.level[self.t] < 0:
                break
            self.itr = list(map(iter, self.graph))
            f = self.dfs(self.s, self.t, self.INF)
            while f > 0:
                flow += f
                f = self.dfs(self.s, self.t, self.INF)
        return flow


x, y, e = map(int, input().split())
graph = [[] for i in range(x + y)]

for i in range(e):
    tmp_x, tmp_y = map(int, input().split())
    graph[tmp_x].append(tmp_y + x)
    graph[tmp_y + x].append(tmp_x)

mb = Bipartite_Matching(graph)
print(mb.max_flow())