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: # Acceptance of input
  
  import sys
  
  file_input = sys.stdin
  
  X, Y, E = map(int, file_input.readline().split())
  
  v_num = X + Y + 2
  
  adj_mat = [[0] * (v_num) for i in range(v_num)]
  
  for line in file_input:
      x, y = map(int, line.split())
      adj_mat[x][X + y] = 1
  
  s = X + Y
  t = s + 1
  
  for i in range(X):
      adj_mat[s][i] = 1
  
  for i in range(X, s):
      adj_mat[i][t] = 1
  
  # Dinic's algorithm
  
  import collections
  
  
  # BFS for residual capacity network to construct level graph
  def bfs(start, goal, parent):
      unvisited = [True] * v_num
      queue = collections.deque()
      queue.append(start)
      unvisited[start] = False
      while queue:
          u = queue.popleft()
          for v, r_capacity in enumerate(adj_mat[u]):
              if unvisited[v] and (r_capacity > 0):
                  parent[v].append(u)
                  queue.append(v)
                  unvisited[v] = False
      return unvisited[goal]
  
  
  # DFS for level graph and construct blocking flow
  def dfs(goal, path, parent, blocking_flow):
      v = path[-1]
      if v == goal:
          aug_path_flow = 10000
          for x, y in zip(path[1:], path[:-1]):
              aug_path_flow = min(aug_path_flow, adj_mat[x][y])
          for x, y in zip(path[1:], path[:-1]):
              adj_mat[x][y] -= aug_path_flow
              adj_mat[y][x] += aug_path_flow
          blocking_flow[0] += aug_path_flow
      else:
          for u in parent[v]:
              path.append(u)
              dfs(goal, path, parent, blocking_flow)
              path.pop()
  
  
  def dinic(source, sink):
      max_flow = 0
      parent = [[] for i in range(v_num)]
      while not bfs(source, sink, parent):
          blocking_flow = [0]
          path = [sink]
          # search in reverse direction from sink
          dfs(source, path, parent, blocking_flow)
          max_flow += blocking_flow[0]
          parent = [[] for i in range(v_num)]
      return max_flow
  
  
  # output
  print(dinic(0, v_num - 1))
  
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"}]