output_description: Print the largest size of the matching.
input_description: |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.
attempt: from collections import deque
  
  
  class Dinic(object):
      __slots__ = ["inf", "v_count", "edges", "iter", "level"]
  
      def __init__(self, v_count: int, edges: list):
          self.inf = 10**9
          self.v_count = v_count
          self.edges = [[] for _ in [0] * v_count]
          self.iter = [0] * v_count
          self.level = None
          self._create_graph(edges)
  
      def _create_graph(self, _edges):
          edges = self.edges
          for origin, dest, cap in _edges:
              edges[origin].append([dest, cap, len(edges[dest])])
              edges[dest].append([origin, 0, len(edges[origin]) - 1])
  
      def solve(self, source: int, sink: int):
          max_flow = 0
  
          while True:
              self.bfs(source)
              if self.level[sink] < 0:
                  return max_flow
  
              self.iter = [0] * self.v_count
              flow = self.dfs(source, sink, self.inf)
  
              while flow > 0:
                  max_flow += flow
                  flow = self.dfs(source, sink, self.inf)
  
      def bfs(self, source: int):
          level, edges = [-1] * self.v_count, self.edges
          level[source] = 0
          dq = deque([source])
          popleft, append = dq.popleft, dq.append
  
          while dq:
              v = popleft()
              for dest, cap, _rev in edges[v]:
                  if cap > 0 > level[dest]:
                      level[dest] = level[v] + 1
                      append(dest)
  
          self.level = level
  
      def dfs(self, source: int, sink: int, flow: int) -> int:
          if source == sink:
              return flow
          while self.iter[source] < len(self.edges[source]):
              dest, cap, rev = edge = self.edges[source][self.iter[source]]
              if cap > 0 and self.level[source] < self.level[dest]:
                  flowed = self.dfs(dest, sink, flow if flow < cap else cap)
                  if flowed > 0:
                      edge[1] -= flowed
                      self.edges[dest][rev][1] += flowed
                      return flowed
              self.iter[source] += 1
  
          return 0
  
  
  if __name__ == "__main__":
      import sys
  
      X, Y, E = map(int, input().split())
      source, sink = X + Y, X + Y + 1
      edges = [(source, i, 1) for i in range(X)] + [(X + i, sink, 1) for i in range(Y)]
      append = edges.append
      for x, y in (map(int, l.split()) for l in sys.stdin):
          append((x, X + y, 1))
      dinic = Dinic(X + Y + 2, edges)
      print(dinic.solve(source, sink))
  
problem_description: Bipartite Matching
  
  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.
samples: [{"input": "3 4 6\n    0 0\n    0 2\n    0 3\n    1 1\n    2 1\n    2 3", "output": "3"}]