Problem:
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. Input  |X|  |Y|  |E|  x 0  y 0  x 1  y 1 : 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.  x i and y i 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. Constraints  1 ≤ |X| , |Y| ≤ 100  0 ≤ |E| ≤ 10,000  Sample Input 1 3 4 6
0 0
0 2
0 3
1 1
2 1
2 3 Sample Output 1 3

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class BipartiteMatching:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.pairA = [-1] * N
        self.pairB = [-1] * M
        self.edge = [[] for _ in range(N)]
        self.was = [0] * N
        self.iter = 0

    def add(self, s, t):
        self.edge[s].append(t)

    def _DFS(self, s):
        self.was[s] = self.iter
        for t in self.edge[s]:
            if self.pairB[t] == -1:
                self.pairA[s] = t
                self.pairB[t] = s
                return True
        for t in self.edge[s]:
            if self.was[self.pairB[t]] != self.iter and self._DFS(self.pairB[t]):
                self.pairA[s] = t
                self.pairB[t] = s
                return True
        return False

    def solve(self):
        res = 0
        while True:
            self.iter += 1
            found = 0
            for i in range(self.N):
                if self.pairA[i] == -1 and self._DFS(i):
                    found += 1
            if not found:
                break
            res += found
        return res


if __name__ == "__main__":
    X, Y, E = map(int, input().split())
    match = BipartiteMatching(X, Y)
    for _ in range(E):
        x, y = map(int, input().split())
        match.add(x, y)
    ans = match.solve()
    print(ans)

Solution (Python):

import sys
from collections import deque

sys.setrecursionlimit(200000)

class Dinic:
    
    def __init__(self,v, inf =10**10):
        self.v = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [-1]*v
        self.ite = [0]*v
    
    def add_edge(self, fr, to, cap):
        self.G[fr].append([to,cap,len(self.G[to])])
        self.G[to].append([fr,0,len(self.G[fr])-1])

    
    def bfs(self,s):
        self.level = [-1]*self.v
        self.level[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            v = Q.popleft()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e[1]>0 and self.level[e[0]]<0:
                    self.level[e[0]] = self.level[v]+1
                    Q.append(e[0])

        
    def dfs(self,v,t,f):
        if v==t:
            return f
        for i in range(self.ite[v],len(self.G[v])):
            self.ite[v] = i
            e = self.G[v][i]
            if e[1]>0 and self.level[v]<self.level[e[0]]:
                d = self.dfs(e[0],t,min(f,e[1]))
                if d>0:
                    e[1] -= d 
                    self.G[e[0]][e[2]][1] += d
                    return d
        return 0
    
    def max_flow(self,s,t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0:
                return flow
            self.ite = [0]*self.v
            f =self.dfs(s,t,self.inf)
            while f>0:
                flow+= f
                f = self.dfs(s,t,self.inf)
            
x,y,e = map(int, input().split( ))
D = Dinic(x+y+2)
for _ in range(e):
    u,w = map(int, input().split( ))
    D.add_edge(u,w+x,1)
for i in range(x+y):
    if i<x:
        D.add_edge(x+y,i,1)
    else:
        D.add_edge(i,x+y+1,1)
ans = D.max_flow(x+y,x+y+1)
print(ans)

Solution (Python):
from typing import Set


def dfs(s: int) -> bool:
    return _dfs(s, set())


def _dfs(v: int, visited: Set[int]) -> bool:
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or _dfs(matched[u], visited):
            matched[u] = v
            return True
    return False


if __name__ == "__main__":
    xn, yn, e = map(lambda x: int(x), input().split())
    edges = [set() for _ in range(xn)]  
    matched = [-1] * yn

    for _ in range(e):
        x, y = map(lambda x: int(x), input().split())
        edges[x].add(y)

    print(sum(map(dfs, range(xn))))

Solution (Python):
from collections import deque


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

    def __init__(self, input_graph: list):
        """重み無し二部グラフinput_graphを入力する"""
        n = len(input_graph)
        self.INF = float("inf")
        
        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())

Solution (Python):
import collections
import queue


class Dinic:
    def __init__(self, N):
        self.N = N
        self.edges = collections.defaultdict(list)
        self.level = [0 for _ in range(self.N)]
        self.iter = [0 for _ in range(self.N)]

    def add(self, u, v, c, directed=True):
        """
        0-indexed
        u = from, v = to, c = cap
        directed = Trueなら、有向グラフである
        """
        if directed:
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u])-1])
        else:  
            self.edges[u].append([v, c, len(self.edges[u])])

    def bfs(self, s):
        self.level = [-1 for _ in range(self.N)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get(s)
            for i in range(len(self.edges[v])):
                e = self.edges[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.put(e[0])

    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.edges[v])):
            self.iter[v] = i
            e = self.edges[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.edges[e[0]][e[2]][1] += d
                    return d
        return 0

    def maxFlow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0 for _ in range(self.N)]
            f = self.dfs(s, t, float('inf'))
            while f > 0:
                flow += f
                f = self.dfs(s, t, float('inf'))


X, Y, E = map(int, input().split())

graph = Dinic(X+Y+2)
s = X+Y
t = X+Y+1
for i in range(X):
    graph.add(s, i, 1)

for i in range(Y):
    graph.add(X+i, t, 1)

for _ in range(E):
    x, y = map(int, input().split())
    graph.add(x, X+y, 1)

print(graph.maxFlow(s, t))

Solution (Python):
class BipartiteMatching:
    def __init__(self, v: int):
        self.v = v
        self.g = [[] for _ in range(v)]
        self.match = [-1] * v
        self.used = [False] * v

    def add_edge(self, u, v):
        self.g[u].append(v)
        self.g[v].append(u)

    def dfs(self, v):
        self.used[v] = True
        for i in range(len(self.g[v])):
            u = self.g[v][i]
            w = self.match[u]

            if w < 0 or (not self.used[w] and self.dfs(w)):
                self.match[u] = v
                self.match[v] = u
                return True

        return False

    def maximum_matching(self):
        res = 0
        self.match = [-1] * self.v
        for i in range(self.v):
            if self.match[i] < 0:
                self.used = [False] * self.v
                if self.dfs(i):
                    res += 1
        return res


if __name__ == '__main__':
    x_size, y_size, e = map(int, input().split())
    b = BipartiteMatching(x_size + y_size)
    for i in range(e):
        x, y = map(int, input().split())
        b.add_edge(x, y + x_size)
    print(b.maximum_matching())

Solution (Python):
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): 
    global lines
    global cost
    global ans

    queue = deque()     
    queue.append([S,INF])
    ed = [True]*N    
    ed[S] = False
    route = [0 for i in range(N)]   
    route[S] = -1

    
    while queue:
        s,flow = queue.pop()
        for t in lines[s]:  
            if ed[t]:
                flow = min(cost[s][t],flow)  
                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:
        
        cost[s][t] -= flow
        if cost[s][t] == 0:
            lines[s].remove(t)

        
        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

Solution (Python):


import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

class BipartiteMatching:
    """
    XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
    edges[x]: xとつながるYの頂点のset
    match1[x]: xとマッチングされたYの頂点
    match2[y]: yとマッチングされたXの頂点
    """

    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.edges = [set() for _ in range(n)]
        self.match1 = [-1] * n
        self.match2 = [-1] * m
 
    def dfs(self, v, visited):
        """
        :param v: X側の未マッチングの頂点の1つ
        :param visited: 空のsetを渡す（外部からの呼び出し時）
        :return: 増大路が見つかればTrue
        """
        for u in self.edges[v]:
            if u in visited:
                continue
            visited.add(u)
            if self.match2[u] == -1 or self.dfs(self.match2[u], visited):
                self.match2[u] = v
                self.match1[v] = u
                return True
        return False
    
    def add(self, a, b):
        self.edges[a].add(b)

    def whois1(self, a):
        """ :param: グループ1の頂点 :return: ペアになるグループ2の頂点 """
        return self.match1[a]

    def whois2(self, a):
        """ :param: グループ2の頂点 :return: ペアになるグループ1の頂点 """
        return self.match2[a]

    def solve(self):
        
        return sum(self.dfs(i, set()) for i in range(self.n))

N,M,E=MAP()
bm=BipartiteMatching(N, M)
for i in range(E):
    x,y=MAP()
    bm.add(x, y)

print(bm.solve())

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007



"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
                print(dist, q)
    return dist

v,e,r = map(int, input().split(" "))
adj = [[] for i in range(v)]
for i in range(e):
    s,t,d = map(int, input().split(" "))
    adj[s].append([t, d])
lis = dijkstra(v, r)
print(lis)
for i in lis:
    print(str(i).upper())
"""


"""
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
                if dist[k] > dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
                    if i == num-1:
                        return False
        if not update:
            break
    return dist

v,e,r = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t,d = map(int, input().split(" "))
    adj.append([s, t, d])
lis = bellman_ford(v, r)
if not lis:
    print("NEGATIVE CYCLE")
else:
    for i in lis:
        print(str(i).upper())
"""


"""
def warshallfloyd(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i]+d[i][k])
v,e = map(int, input().split())
d = [[float("inf") for j in range(v)] for i in range(v)]
for i in range(v):
    d[i][i] = 0
for i in range(e):
    s, t, c = map(int, input().split())
    d[s][t] = c
warshallfloyd(v)
for i in range(v):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        quit()
for i in d:
    for j in range(v):
        if j < v-1:
            print(str(i[j]).upper(), end = " ")
        else:
            print(str(i[j]).upper())
"""



"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
v,e = LI()
c = LIR(e)
c.sort(key = lambda x:x[2])
par = [i for i in range(v)]
rank = [0 for i in range(v)]
k = 0
ans = 0
for a,b,w in c:
    if not same(a,b):
        k += 1
        unite(a,b)
        ans += w
    if k == v-1:
        break
print(ans)
"""


"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank(x) < rank(y):
        par[x] = y
    else:
        par[y] = x
        if rank(x) == rank(y):
            rank[x] += 1
"""











"""
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
            if dist[k] > dist[j] + l:
                dist[k] = dist[j] + l
                update = True
                if i == num-1:
                    return False
        if not update:
            break
    return True

v, e = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t = map(int, input().split(" "))
    adj.append([s, t, -1])
for i in range(v):
    if not bellman_ford(v,i):
        print(1)
        quit()
print(0)
"""






"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = II()
adj = [[] for i in range(n)]
for i in range(n-1):
    s,t,w = LI()
    adj[s].append([t, w])
    adj[t].append([s, w])
d = dijkstra(n,0)
i = d.index(max(d))
d2 = dijkstra(n,i)
print(max(d2))
"""


"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = int(input())
adj = [[] for i in range(n)]
for i in range(n-1):
    s, t, w = map(int, input().split(" "))
    adj[s].append([t, w])
    adj[t].append([s, w])
for i in range(n):
    s = dijkstra(n,i)
    print(max(s))
"""









"""
def bfs(s,g,n):
    bfs_map = [-1 for i in range(n)]
    bfs_map[s] = 0
    q = deque()
    q.append(s)
    fin = False
    while q:
        x = q.popleft()
        for y in range(n):
            if c[x][y] > 0 and bfs_map[y] < 0:
                bfs_map[y] = bfs_map[x]+1
                if y == g:
                    fin = True
                    break
                q.append(y)
        if fin:
            break

    if bfs_map[g] == -1:
        return [None,0]
    path = [None for i in range(bfs_map[g]+1)]
    m = float("inf")
    path[bfs_map[g]] = g
    y = g
    for i in range(bfs_map[g])[::-1]:
        for x in range(n+1):
            if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                path[i] = x
                if c[x][y] < m:
                    m = c[x][y]
                y = x
                break
    return [path,m]

def ford_fulkerson(s,g,c,n):
    while 1:
        p,m = bfs(s,g,n)
        if not m:break
        for i in range(len(p)-1):
            c[p[i]][p[i+1]] -= m
            c[p[i+1]][p[i]] += m
    return sum(c[g])

n,e = LI()
c = [[0 for i in range(n)] for j in range(n)]
for i in range(e):
    a,b,w = LI()
    if a != n-1:
        c[a][b] = w
print(ford_fulkerson(0,n-1,c,n))
"""





def bfs(s,g,n):
    bfs_map = [-1 for i in range(n)]
    bfs_map[s] = 0
    q = deque()
    q.append(s)
    fin = False
    while q:
        x = q.popleft()
        for y in range(n):
            if c[x][y] > 0 and bfs_map[y] < 0:
                bfs_map[y] = bfs_map[x]+1
                if y == g:
                    fin = True
                    break
                q.append(y)
        if fin:
            break

    if bfs_map[g] == -1:
        return [None,0]
    path = [None for i in range(bfs_map[g]+1)]
    m = float("inf")
    path[bfs_map[g]] = g
    y = g
    for i in range(bfs_map[g])[::-1]:
        for x in range(n+1):
            if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                path[i] = x
                if c[x][y] < m:
                    m = c[x][y]
                y = x
                break
    return [path,m]

def ford_fulkerson(s,g,c,n):
    while 1:
        p,m = bfs(s,g,n)
        if not m:break
        for i in range(len(p)-1):
            c[p[i]][p[i+1]] -= m
            c[p[i+1]][p[i]] += m
    return sum(c[g])

x,y,e = LI()
c = [[0 for i in range(x+y+2)] for j in range(x+y+2)]
for i in range(x):
    c[0][i+1] = 1
for i in range(y):
    c[x+i+1][x+y+1] = 1
for i in range(e):
    a,b = LI()
    c[a+1][x+b+1] = 1
print(ford_fulkerson(0,x+y+1,c,x+y+2))

Solution (Python):
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))

Solution (Python):
import sys
from collections import deque
 
 
class MaxFlow:
    class Edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev
 
    def __init__(self, node_size, inf):
        self._node = node_size
        self._inf = inf
        self._level = [-1]*self._node
        self._iter = [0]*self._node
        self._graph = [[] for _ in range(self._node)]
 
    def add_edge(self, from_, to, cap):
        self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
        self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_])-1))
 
    def bfs(self, start):
        self._level = [-1]*self._node
        que = deque()
        self._level[start] = 0
        que.append(start)
        while que:
            cur_vertex = que.popleft()
            for e in self._graph[cur_vertex]:
                if self._level[e.to] < 0 < e.cap:
                    self._level[e.to] = self._level[cur_vertex] + 1
                    que.append(e.to)
 
    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:
            return flow
        while self._iter[cur_vertex] < len(self._graph[cur_vertex]):
            e = self._graph[cur_vertex][self._iter[cur_vertex]]
            if e.cap > 0 and self._level[cur_vertex] < self._level[e.to]:
                flowed = self.dfs(e.to, end_vertex, min(flow, e.cap))
                if flowed > 0:
                    e.cap -= flowed
                    self._graph[e.to][e.rev].cap += flowed
                    return flowed
            self._iter[cur_vertex] += 1
        return 0
 
    def solve(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self._level[sink] < 0:
                return flow
            self._iter = [0]*self._node
            while True:
                f = self.dfs(source, sink, self._inf)
                if f == 0:
                    break
                flow += f
 
 
class BipartiteMatching:
    def __init__(self, size1, size2):
        self._u_size, self. _v_size = size1, size2
        self.mf = MaxFlow(self._u_size+self. _v_size+2, min(self._u_size, self._v_size))
        for i in range(self._u_size):
            self.mf.add_edge(0, i+1, 1)
        for i in range(self._v_size):
            self.mf.add_edge(self._u_size+i+1, self._u_size+self._v_size+1, 1)
 
    def add_edge(self, from_, to):
        self.mf.add_edge(from_+1, to+self._u_size+1, 1)
 
    def solve(self):
        return self.mf.solve(0, self._u_size+self._v_size+1)
 
if __name__=='__main__':
    x, y, m = map(int, sys.stdin.readline().split())
    bm = BipartiteMatching(x, y)
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        bm.add_edge(u, v)
    print(bm.solve())

Solution (Python):




from heapq import heappush, heappop


class Edge:
    __slots__ = ('src', 'dest', 'capacity', 'flow', 'cost')

    def __init__(self, v, w, capacity, cost=0):
        self.src = v
        self.dest = w
        self.capacity = capacity
        self.cost = cost
        self.flow = 0

    def other(self, v):
        if v == self.src:
            return self.dest
        else:
            return self.src

    def residual_capacity(self, v):
        if v == self.src:
            return self.capacity - self.flow
        else:
            return self.flow

    def cost_from(self, v):
        if v == self.src:
            return self.cost
        else:
            return -self.cost

    def add_flow(self, v, f):
        if v == self.src:
            self.flow += f
        else:
            self.flow -= f

    def __str__(self):
        return "{} {} {} {} {}".format(self.src, self.dest, self.capacity,
                                       self.cost, self.flow)


class Network:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)
        self._edges[edge.dest].append(edge)

    def adj(self, v):
        return self._edges[v]

    def flow(self, v):
        return sum(e.flow for e in self.adj(v) if e.src == v)

    def cost(self):
        cost = 0
        for v in range(self.v):
            for e in self.adj(v):
                if e.src == v:
                    cost += e.flow * e.cost
        return cost

    def __str__(self):
        s = ''
        for v in range(self.v):
            for e in self.adj(v):
                s += "{} {}\n".format(v, e)

        return s


def max_flow(network, s, t):
    def augment_path():
        marked = [False] * network.v
        edge_to = [None] * network.v
        n = 0
        heap = [(-10**6, s, n, None)]
        while heap:
            cap, v, _, e = heappop(heap)
            edge_to[v] = e
            if v == t:
                return (-cap, edge_to)
            if not marked[v]:
                marked[v] = True
                for ne in network.adj(v):
                    n += 1
                    w = ne.other(v)
                    c = ne.residual_capacity(v)
                    if not marked[w] and c > 0:
                        heappush(heap, (max(-c, cap), w, n, ne))

        return (0, [])

    while True:
        cap, path = augment_path()
        if cap == 0:
            break
        v = t
        e = path[t]
        while e is not None:
            v = e.other(v)
            e.add_flow(v, cap)
            e = path[v]

    return network.flow(s)


def run():
    n, m, e = [int(i) for i in input().split()]
    s, t = 0, n+m+1
    net = Network(n+m+2)
    for i in range(n):
        net.add(Edge(s, i+1, 1))
    for j in range(m):
        net.add(Edge(j+1+n, t, 1))

    for _ in range(e):
        x, y = [int(i) for i in input().split()]
        edge = Edge(x+1, y+1+n, 1)
        net.add(edge)

    print(max_flow(net, s, t))


if __name__ == '__main__':
    run()