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
from queue import deque

sys.setrecursionlimit(200000)


def hierarchize(source):
    global hierarchy
    hierarchy = [-1] * n
    queue = deque([(0, source)])
    while queue:
        h, v = queue.popleft()
        if hierarchy[v] != -1:
            continue
        hierarchy[v] = h
        if v == sink:
            return True
        queue.extend((h + 1, target)
                     for remain, target, _ in edges[v] if hierarchy[target] == -1 and remain)
    return False


def augment(v, limit):
    if v == sink:
        return limit
    res = 0
    for e in edges[v]:
        remain, target, idx = e
        if remain == 0 or hierarchy[v] >= hierarchy[target]:
            continue
        aug = augment(target, min(limit, remain))
        e[0] -= aug
        edges[target][idx][0] += aug
        res += aug
        limit -= aug
        if not limit:
            break
    return res


xn, yn, e = map(int, input().split())
n = xn + yn + 2
sink = n - 1
edges = [[] for _ in range(n)]

hierarchy = [-1] * n

for x in range(xn):
    xi = x + 1
    edges[0].append([1, xi, 0])
    edges[xi].append([0, 0, x])
for y in range(yn):
    yi = xn + y + 1
    edges[yi].append([1, sink, y])
    edges[sink].append([0, yi, 0])

for _ in range(e):
    x, y = map(int, input().split())
    xi, yi = x + 1, xn + y + 1
    ex, ey = edges[xi], edges[yi]
    lx, ly = len(ex), len(ey)
    ex.append([1, yi, ly])
    ey.append([0, xi, lx])

res = 0
while hierarchize(0):
    res += augment(0, 100)
print(res)

Solution (Python):
def dfs(s):
    return _dfs(s, set())


def _dfs(v, visited):
    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


xn, yn, e = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn

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

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

Solution (Python):
def dfs(v, edges, visited, matched):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], edges, visited, matched):
            matched[u] = v
            return True
    return False


xn, yn, e = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn

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

print(sum(dfs(s, edges, set(), matched) for s in range(xn)))

Solution (Python):
def dfs(v, visited):
    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


xn, yn, e = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn

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

print(sum(dfs(s, set()) for s in range(xn)))

Solution (Python):
def dfs(v, visited):
    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


xn, yn, e = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn

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

print(sum(map(lambda s: dfs(s, set()), range(xn))))

Solution (Python):
import collections
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]
    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 add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<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
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

X, Y, E = map(int, input().split())
dinic = Dinic(2+X+Y)
for i in range(X):
    dinic.add_edge(0, 2+i, 1)
for i in range(Y):
    dinic.add_edge(2+X+i, 1, 1)
for i in range(E):
    x, y = map(int, input().split())
    dinic.add_edge(2+x, 2+X+y, 1)
print(dinic.max_flow(0, 1))

Solution (Python):
from collections import defaultdict
def dfs(here,used,match,connect):
    used[here] = 1
    for near in connect[here]:
        m = match[near]
        if m < 0 or (not used[m] and dfs(m,used,match,connect)):
            match[here] = near
            match[near] = here
            return 1
    return 0

a_num, b_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
all_v = a_num + b_num
match = [-1 for n in range(all_v)]
for _ in range(e_num):
    v1, v2 = (int(n) for n in input().split(" "))
    v2 += a_num
    connect[v1].append(v2)
    connect[v2].append(v1)
answer = 0
for i in range(all_v):
    if match[i] < 0:
        used = [0 for n in range(all_v)]
        if dfs(i,used,match,connect):
            answer += 1
print(answer)

Solution (Python):

"""
Matching - Bipartite Matching
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A&lang=jp

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline
edge = namedtuple('edge', ['to', 'cap', 'rev'])


def add_edge(G, f, t, c):
    G[f].append(edge(t, c, len(G[t])))
    G[t].append(edge(f, 0, len(G[f]) - 1))


def dfs(G, used, v, t, f):
    if v == t:
        return f
    used[v] = True
    for i in range(len(G[v])):
        e = G[v][i]
        if (not used[e.to]) and (e.cap > 0):
            d = dfs(G, used, e.to, t, min(f, e.cap))
            if d > 0:
                G[v][i] = edge(e.to, e.cap - d, e.rev)
                G[e.to][e.rev] = edge(G[e.to][e.rev].to, G[e.to][e.rev].cap + d, G[e.to][e.rev].rev)
                return d
    return 0


def max_flow(G, V, s, t):
    flow = 0
    while True:
        used = [False] * V
        f = dfs(G, used, s, t, float('inf'))
        if f == 0:
            return flow
        flow += f


def main(args):
    """
    - 追加したソースノードID: 0
    - Xグループ: 1〜X
    - Yグループ: X+1〜X+Y
    - 追加したシンクノードID: X+Y+1
    として、ノード0 → X+Y+1 への最大流を求める
    """
    X, Y, E = map(int, input().split())
    G = [[] for _ in range(X+Y+2)]

    for li in range(E):
        x, y = map(int, input().split())
        add_edge(G, x+1, X+y+1, 1)

    for x in range(1, X+1):
        add_edge(G, 0, x, 1)       
    for y in range(X+1, X+Y+1):
        add_edge(G, y, X+Y+1, 1)   


    ans = max_flow(G, X+Y+2, 0, X+Y+1) 
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
class BipartiteMatching:
    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]

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

    def dfs(self, u):
        self.used[u] = True
        for v in self.G[u]:
            w = self.match[v]
            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 bipartite_matching(self):
        res = 0
        self.match = [-1] * self.V
        for v in range(self.V):
            if self.match[v] == -1:
                self.used = [False] * self.V
                if self.dfs(v):
                    res += 1
        return res

X, Y, E = map(int, input().split())
bm = BipartiteMatching(X+Y)
for _ in range(E):
    x, y = map(int, input().split())
    bm.add_edge(x, X + y)
print(bm.bipartite_matching())

Solution (Python):
class Node():
    def __init__(self):
        self.edge = []
        self.level = None
        self.par = None
        self.cap = 10**18

class Edge():
    def __init__(self, to, cap, rev=None):
        self.to = to
        self.cap = cap
        self.rev = rev

from collections import deque

class BipartiteMatching():
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.inf = 10**18
        self.source = Node()
        self.sink = Node()
        self.lt = [Node() for _ in range(n)]
        self.rt = [Node() for _ in range(m)]
        for i in range(n):
            edge = Edge(self.lt[i], 1)
            rev = Edge(self.source, 0)
            edge.rev, rev.rev = rev, edge
            self.source.edge.append(edge)
            self.lt[i].edge.append(rev)
        for i in range(m):
            edge = Edge(self.sink, 1)
            rev = Edge(self.rt[i], 0)
            edge.rev, rev.rev = rev, edge
            self.rt[i].edge.append(edge)
            self.sink.edge.append(rev)

    def add(self, x, y):
        lt = self.lt[x]
        rt = self.rt[y]
        edge = Edge(rt, 1)
        rev = Edge(lt, 0)
        edge.rev, rev.rev = rev, edge
        lt.edge.append(edge)
        rt.edge.append(rev)

    def maximum_matching(self):
        flow = 0
        while True:
            queue = deque([self.source])
            self.source.level = 0
            self.sink.level = None
            for i in range(self.n):
                self.lt[i].level = None
            for i in range(self.m):
                self.rt[i].level = None
            while queue:
                node = queue.popleft()
                for edge in node.edge:
                    to = edge.to
                    if edge.cap and to.level is None:
                        to.level = node.level + 1
                        queue.append(to)
            if self.sink.level is None: break
            stack = [self.source]
            self.source.par = None
            self.sink.par = None
            for i in range(self.n):
                self.lt[i].par = None
            for i in range(self.m):
                self.rt[i].par = None
            while stack:
                node = stack.pop()
                if node is self.sink:
                    break
                for edge in node.edge:
                    to = edge.to
                    if edge.cap and node.level < to.level:
                        to.par = edge.rev
                        
                        stack.append(to)
            node = self.sink
            delta = node.cap
            while node is not self.source:
                node.par.cap = 1
                node.par.rev.cap = 0
                node = node.par.to
            flow += 1
        return flow

import sys
input = sys.stdin.readline

N, M, E = map(int, input().split())
bm = BipartiteMatching(N, M)
for _ in range(E):
    x, y = map(int, input().split())
    bm.add(x, y)
print(bm.maximum_matching())

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    X,Y,E = LI()

    edge = [set() for _ in range(X+Y+2)]

    for _ in range(E):
        a,b = LI()
        i = a + 1
        j = b + X + 1
        edge[i].add(j)
    for i in range(1,X+1):
        edge[0].add(i)
    for j in range(X+1,X+Y+1):
        edge[j].add(X+Y+1)

    ans = 0
    while True:
        node = [-2] * (X + Y + 2)
        node[0] = -1
        q = collections.deque()
        q.append(0)
        while q:
            u = q.pop()
            for v in edge[u]:
                if v == X + Y + 1:
                    ans += 1
                    node[v] = u
                    break
                if node[v] < -1:
                    node[v] = u
                    q.append(v)
            else:
                continue
            break
        else:
            break

        u = X + Y + 1
        while node[u] >= 0:
            edge[node[u]].remove(u)
            edge[u].add(node[u])
            u = node[u]


    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def outer(x,match,phi):
    if(match[x]==x or phi[match[x]]!=match[x]):
        return True
    return False
    
def inner(x,match,phi):
    if(match[x]!=x and phi[match[x]]==match[x] and phi[x]!=x):
        return True
    return False

def F(x,match,phi):
    if(match[x]!=x and phi[match[x]]==match[x] and phi[x]==x):
        return True
    return False
       
def disjoint(x,y,V,phi,match):
    usedx=[False]*V
    prex=match[x]
    while not (usedx[x] and usedx[prex]) :
        usedx[prex]=True
        usedx[x]=True
        x=phi[prex]
        prex=match[x]
    usedy=[False]*V
    prey=match[y]
    while not (usedy[y] and usedy[prey]) :
        usedy[y]=True
        usedy[prey]=True
        if usedx[y] or usedx[prey]:
            return False
        prey=match[y]
        y=phi[prey]
    return True
    
def shrink(x,y,match,rho,phi,V):
    r=firstvertex(x,y,match,phi,rho,V)
    v=match[x]    
    if x!=r and x!=v:
        while True:
            if rho[phi[v]]!=r:
                phi[phi[v]]=v
            if(phi[v]==r or match[phi[v]]==r):
                break
            v=match[phi[v]]
    v=match[y]
    if y!=r and y!=v:
        while True:
            if rho[phi[v]]!=r:
                phi[phi[v]]=v
            if(phi[v]==r or match[phi[v]]==r):
                break
            v=match[phi[v]]

    if rho[x]!=r:
        phi[x]=y
    if rho[y]!=r:
        phi[y]=x
        
    used=[False]*V
    used[r]=True
    while x!=r or y!=r: 
        used[x]=True
        used[y]=True
        if(x!=r):
            x=match[x]
        if y!=r:
            y=match[y]
        used[x]=True
        used[y]=True
        if x!=r:
            x=phi[x]
        if y!=r:
            y=phi[y]
    for i in range(V):
        if used[rho[i]] :
            rho[i]=r
    
def firstvertex(x,y,match,phi,rho,V):
    usedx=[False]*V
    usedy=[False]*V
    flag=True
    while True:
        if usedy[x] and rho[x]==x:
            return x
        usedx[x]=True
        if usedx[y] and rho[y]==y:
            return y
        usedy[y]=True
        if flag:
            x=match[x]
            y=match[y]
            flag=False
        else:
            x=phi[x]
            y=phi[y]
            flag=True
       
def augment(x,y,match,phi,V):
    v=match[x]
    used=[False]*V
    used[x]=True
    while not used[v]:
        used[v]=True
        used[phi[v]]=True
        tmp=match[phi[v]]
        match[phi[v]]=v
        match[v]=phi[v]
        v=tmp
    v=match[y]
    used=[False]*V
    used[y]=True
    while not used[v]:
        used[v]=True
        used[phi[v]]=True
        tmp=match[phi[v]]
        match[phi[v]]=v
        match[v]=phi[v]
        v=tmp
    match[x]=y
    match[y]=x
    
    
def Edmonds(graph,V):
    match=[i for i in range(V)]
    phi=[i for i in range(V)]
    rho=[i for i in range(V)]
    scanned=[False]*V
    
    while True:

        flag=True
        for i in range(V):
            if (not scanned[i]) and outer(i,match,phi):
                x=i
                flag=False
                break
        if flag:
            break
        for y in graph[x]:
            if F(y,match,phi):
                
                phi[y]=x
                continue
            if not(outer(y,match,phi) and rho[y]!=rho[x]):
                continue
                
            if disjoint(x,y,V,phi,match):
                
                augment(x,y,match,phi,V)
                scanned=[False]*V
                rho=[i for i in range(V)]
                phi=[i for i in range(V)]
                flag=True
                break
            
            shrink(x,y,match,rho,phi,V)
        if not flag:
            scanned[x]=True
    cnt=0
    for i in range(V):
        if match[i]!=i:
            cnt+=1

    return int(cnt/2)
        




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

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

cnt=Edmonds(graph,v)
print(cnt)

Solution (Python):

class Dinic:
    def __init__(self, len_X, len_Y):
        self.len_X, self.len_Y = len_X, len_Y
        self.edges = [[] for _ in range(len_X)]
        self.matched = [-1] * len_Y
        self.visited = set()

    def add_edge(self, x, y):
        self.edges[x].append(y)

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

    def solve(self):
        res = 0
        for x in range(self.len_X):
            self.visited = set()
            res += self.dfs(x)
        return res




len_X, len_Y, E = map(int, input().split())     


dinic = Dinic(len_X, len_Y)

for _ in range(E):
    x, y = map(int, input().split())
    dinic.add_edge(x,y)


print(dinic.solve())

Solution (Python):



class BipartiteMatching():
    def __init__(self, V1, V2):
        self.V1 = V1
        self.V2 = V2
        self.V = V1 + V2
        self.graph = [[] for _ in range(V1+V2)]
    
    def add_edge(self, v1, v2):
        v2 += self.V1
        self.graph[v1].append(v2)
        self.graph[v2].append(v1)

    
    def dfs(self, s):
        self.par = [None]*self.V
        self.used = [False]*self.V
        self.used[s] = True
        self.stack = [s]
        while self.stack:
            v = self.stack.pop()
            for nv in self.graph[v]:
                w = self.match[nv]
                if w < 0:
                    while True:
                        self.match[v] = nv
                        self.match[nv] = v
                        if v == s: return True
                        v, nv = self.par[v]
                elif not self.used[w]:
                    self.par[w] = (v, nv)
                    self.used[w] = True
                    self.stack.append(w)
        return False

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


if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    V1, V2, E = map(int, input().split())
    bm = BipartiteMatching(V1, V2)
    for _ in range(E):
        a, b = map(int, input().split())
        bm.add_edge(a, b)
    print(bm.bipartite_matching())

Solution (Python):
import sys,collections
sys.setrecursionlimit(100000)

INF = float("inf")

X,Y,E = map(int,sys.stdin.readline().split())
xy = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) 

V = X+Y+2
uvc = [[x+1,y+X+1,1] for x,y in xy]
for i in range(X):
    uvc.append([0,i+1,1])
for i in range(Y):
    uvc.append([X+i+1,V-1,1])
G = {i:{} for i in range(V)}
mG = {i:{} for i in range(V)}

for u,v,c in uvc:
    G[u][v] = c
    G[v][u] = 0 
    mG[u][v] = 0
    mG[v][u] = 0


def dfs(current,flow):
    if current == V-1:
        return flow
    visited.add(current)
    for nex,nex_c in G[current].items():
        if not nex in visited and nex_c != 0:
            f = dfs(nex,min(flow,nex_c))
            if f != 0:
                mG[current][nex] = mG[current][nex] + f
                G[current][nex] = G[current][nex] - f
                G[nex][current] = G[nex][current] + f
                return f
    return 0

visited = set()
while dfs(0,INF) != 0:
    visited = set()
    
    
    pass
print(sum(mG[0].values()))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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()
D = Dinic(X+Y+2)
s = X+Y
t = X+Y+1

for i in range(X):
	D.add_edge(s, i, 1)

for i in range(Y):
	D.add_edge(X+i, t, 1)

for _ in range(E):
	x, y = MAP()
	D.add_edge(x, X+y, 1)

print(D.max_flow(s, t))

Solution (Python):
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

x,y,e = map(int, input().split())
s = x+y
t = x+y+1
dinic = Dinic(x+y+2)

for _ in range(e):
    xv,yv = map(int, input().split())
    dinic.add_edge(xv,x+yv,1)

for xv in range(x):
    dinic.add_edge(s,xv,1)
for yv in range(x,x+y):
    dinic.add_edge(yv,t,1)

print(dinic.flow(s,t))

Solution (Python):
from collections import deque

class MaxFlow:
    class Edge:
        def __init__(self,to,cap,rev):
            self.to = to
            self.cap = cap
            self.rev = rev

    def __init__(self,n,inf = 10**9+7):
        self.n = n
        self.inf = inf
        self.level = [-1]*n
        self.iter = [0]*n
        self.e = [[] for _ in range(n)]

    def add_edge(self, from_, to, cap):
        self.e[from_].append(self.Edge(to, cap, len(self.e[to])))
        self.e[to].append(self.Edge(from_, 0, len(self.e[from_])-1))

    def bfs(self, start):
        self.level = [-1]*self.n
        dq = deque()
        self.level[start] = 0
        dq.append(start)
        while dq:
            cur_vertex = dq.popleft()
            for edge in self.e[cur_vertex]:
                if edge.cap > 0 > self.level[edge.to]:
                    self.level[edge.to] = self.level[cur_vertex] + 1
                    dq.append(edge.to)

    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:return flow
        while self.iter[cur_vertex] < len(self.e[cur_vertex]):
            edge = self.e[cur_vertex][self.iter[cur_vertex]]
            if edge.cap > 0 and self.level[cur_vertex] < self.level[edge.to]:
                flowed = self.dfs(edge.to, end_vertex, min(flow, edge.cap))
                if flowed > 0:
                    edge.cap -= flowed
                    self.e[edge.to][edge.rev].cap += flowed
                    return flowed
            self.iter[cur_vertex] += 1
        return 0

    def compute(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:return flow
            self.iter = [0]*self.n
            while True:
                f = self.dfs(source, sink, self.inf)
                if f == 0:break
                flow += f

def main():
    x,y,e = map(int,input().split())
    mf = MaxFlow(x+y+2)
    s = x+y
    t = s+1
    for _ in range(e):
        a,b = map(int,input().split())
        mf.add_edge(a,b+x,1)
    for i in range(x):
        mf.add_edge(s,i,1)
    for i in range(y):
        mf.add_edge(i+x,t,1)
    print (mf.compute(s,t))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

class HopcroftKarp:
    def __init__(self, N0, N1):
        self.N0 = N0; self.N1 = N1
        self.N = N = 2 + N0 + N1
        self.E = E = [[] for _ in range(N)]
        for end in range(N0): 
            v = end + 2
            E[0].append([v, 1, len(E[v])])
            E[v].append([0, 0, len(E[0]) - 1])
        for init in range(N1): 
            u = init + N0 + 2
            E[u].append([1, 1, len(E[1])])
            E[1].append([u, 0, len(E[u]) - 1])
    
    def add_edge(self, p1, p2):
        '''
            e[0] = the head vertex of e,
            e[1] = current capacity of e,
            e[2] = the index of reverse edge of e.
        '''
        p1 += 2; p2 += self.N0 + 2
        self.E[p1].append([p2, 1, len(self.E[p2])])
        self.E[p2].append([p1, 0, len(self.E[p1]) - 1])
    
    def _exist_augpath(self):
        self.level = level = [-1] * self.N 
        E = self.E
        q = deque([(0, 0)]) 
        while q:
            v, lv = q.popleft()
            if level[v] < 0: 
                level[v] = lv
                for u, cap, _ in E[v]:
                    if cap == 0 or level[u] >= 0: continue
                    q.append((u, lv + 1))
        return level[1] >= 0
    
    def _blocking_flow(self):
        s = 0; t = 1
        aug_flow = 0
        finished = [False] * self.N
        parent = [-1] * self.N
        revs = [-1] * self.N
        bottleneck = -1; temp_flow = 0
        level, E = self.level, self.E
        stack = [(s, -1, float('inf'), -1, 0)] 
        while stack:
            v, p, f, rev, st = stack.pop()
            if temp_flow and v != bottleneck: continue
            if st == 0 and not finished[v]:
                parent[v] = p; revs[v] = rev
                if temp_flow: 
                    f -= temp_flow; temp_flow = 0; bottleneck = -1
                if v == t: 
                    aug_flow += f
                    if p != -1: stack += [(v, p, f, rev, 3)]
                    continue
                n_children = 0
                for u, cap, rev_idx in E[v]:
                    if cap == 0 or finished[u] or level[u] != level[v] + 1: continue
                    if n_children == 0:
                        stack += [(v, p, 0, rev, 2), (u, v, min(f, cap), rev_idx, 0)]
                        n_children += 1
                    else:
                        stack += [(v, p, 0, rev, 1), (u, v, min(f, cap), rev_idx, 0)]
                        n_children += 1
                if n_children == 0: 
                    finished[v] = True
            elif st == 1: 
                continue
            elif st == 2: 
                finished[v] = True
            else: 
                rev_e = E[v][rev]; e = E[p][rev_e[2]]
                e[1] -= f; rev_e[1] += f
                if e[1] == 0: bottleneck = p
                if parent[p] != -1: stack += [(p, parent[p], f, revs[p], 3)]
                else: temp_flow = f
        return aug_flow
    
    def max_matching(self):
        matching = 0
        exist_augpath, blocking_flow = self._exist_augpath, self._blocking_flow
        while True:
            if not exist_augpath(): break
            matching += blocking_flow()
        return matching

N0, N1, M = map(int, input().split())
hk = HopcroftKarp(N0, N1)
for _ in range(M):
    u, v = map(int, input().split())
    hk.add_edge(u, v)
print(hk.max_matching())