human
Give me a Python code to find the size of the matching which has the largest size given the following:
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
from
assistant
#Here is Python code to find the size of the matching which has the largest size.
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...