def dinic(self, src, sink):

    def bfs():
        lv = {src: 0}
        q = deque([src])
        while q:
            u = q.popleft()
            for (v, e) in self.edges[u].items():
                if ((e['capacity'] == 0) or (v in lv)):
                    continue
                lv[v] = (lv[u] + 1)
                q.append(v)
        return lv

    def flow_to_sink(u, flow_in):
        if (u == sink):
            return flow_in
        flow = 0
        for (v, e) in self.edges[u].items():
            cap = e['capacity']
            if ((cap == 0) or (lv[v] <= lv[u])):
                continue
            f = flow_to_sink(v, min(flow_in, cap))
            if (not f):
                continue
            self.edges[u][v]['capacity'] -= f
            if ((v in self.edges) and (u in self.edges[v])):
                self.edges[v][u]['capacity'] += f
            else:
                self.add_edge(v, u, capacity=f)
            flow_in -= f
            flow += f
        return flow
    flow = 0
    while True:
        lv = bfs()
        if (not (sink in lv)):
            return flow
        flow += flow_to_sink(src, inf)
def dinic(self, src, sink):

    def bfs():
        lv = {src: 0}
        q = deque([src])
        while q:
            u = q.popleft()
            for (v, e) in self.edges[u].items():
                if ((e['capacity'] == 0) or (v in lv)):
                    continue
                lv[v] = (lv[u] + 1)
                q.append(v)
        return lv

    def flow_to_sink(u, flow_in):
        if (u == sink):
            return flow_in
        flow = 0
        for (v, e) in self.edges[u].items():
            cap = e['capacity']
            if ((cap == 0) or (lv[v] <= lv[u])):
                continue
            f = flow_to_sink(v, min(flow_in, cap))
            if (not f):
                continue
            self.edges[u][v]['capacity'] -= f
            if ((v in self.edges) and (u in self.edges[v])):
                self.edges[v][u]['capacity'] += f
            else:
                self.add_edge(v, u, capacity=f)
            flow_in -= f
            flow += f
        return flow
    flow = 0
    while True:
        lv = bfs()
        if (not (sink in lv)):
            return flow
        flow += flow_to_sink(src, inf)