#### Dinic

K
```INF = float("inf")

class Dinic:
def __init__(self, n):
self.lvl =  * n
self.ptr =  * n
self.q =  * n
self.adj = [[] for _ in range(n)]

"""
Here we will add our edges containing with the following parameters:
vertex closest to source, vertex closest to sink and flow capacity
through that edge ...
"""

def add_edge(self, a, b, c, rcap=0):

# This is a sample depth first search to be used at max_flow
def depth_first_search(self, vertex, sink, flow):
if vertex == sink or not flow:
return flow

if self.lvl[e] == self.lvl[vertex] + 1:
p = self.depth_first_search(e, sink, min(flow, e - e))
if p:
return p
self.ptr[vertex] = self.ptr[vertex] + 1
return 0

# Here we calculate the flow that reaches the sink
def max_flow(self, source, sink):
flow, self.q = 0, source
for l in range(31):  # noqa: E741  l = 30 maybe faster for random data
while True:
self.lvl, self.ptr =  * len(self.q),  * len(self.q)
qi, qe, self.lvl[source] = 0, 1, 1
while qi < qe and not self.lvl[sink]:
v = self.q[qi]
qi += 1
if not self.lvl[e] and (e - e) >> (30 - l):
self.q[qe] = e
qe += 1
self.lvl[e] = self.lvl[v] + 1

p = self.depth_first_search(source, sink, INF)
while p:
flow += p
p = self.depth_first_search(source, sink, INF)

if not self.lvl[sink]:
break

return flow

# Example to use

"""
Will be a bipartite graph, than it has the vertices near the source(4)
and the vertices near the sink(4)
"""
# Here we make a graphs with 10 vertex(source and sink includes)
graph = Dinic(10)
source = 0
sink = 9
"""
Now we add the vertices next to the font in the font with 1 capacity in this edge
(source -> source vertices)
"""
for vertex in range(1, 5):
"""
We will do the same thing for the vertices near the sink, but from vertex to sink
(sink vertices -> sink)
"""
for vertex in range(5, 9):
"""
Finally we add the verices near the sink to the vertices near the source.
(source vertices -> sink vertices)
"""
for vertex in range(1, 5):  