class MaximumFlow:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {}
        for i in self.nodes:
            for j in self.nodes:
                self.graph[(i, j)] = 0

    def add_edge(self, node_a, node_b, capacity):
        self.graph[(node_a, node_b)] += capacity

    def add_flow(self, node, sink, flow):
        if node in self.seen:
            return 0
        self.seen.add(node)
        if node == sink:
            return flow
        for next_node in self.nodes:
            if self.flow[(node, next_node)] > 0:
                new_flow = min(flow, self.flow[(node, next_node)])
                inc = self.add_flow(next_node, sink, new_flow)
                if inc > 0:
                    self.flow[(node, next_node)] -= inc
                    self.flow[(next_node, node)] += inc
                    return inc
        return 0

    def construct(self, source, sink):
        self.flow = self.graph.copy()
        total = 0
        while True:
            self.seen = set()
            add = self.add_flow(source, sink, float("inf"))
            if add == 0:
                break
            total += add
        return total


class Planets:
    def __init__(self, n):
        self.n = n
        self.mf = MaximumFlow([x for x in range(1, n + 1)])

    def add_teleport(self, a, b):
        self.mf.add_edge(a, b, 1)

    def min_removals(self):
        return self.mf.construct(1, self.n)


class Planets2:
    def __init__(self, n):
        self.n = n
        self.nodes = [x for x in range(1, n + 1)]
        self.graph = {}

    def add_teleport(self, a, b):
        self.graph[b] = self.graph[b].append(a) if self.graph.get(b) else [a]

    def min_removals(self):
        nodes = self.graph[self.n]
        lowest_teleports = 0
        for x in nodes:
            pass

        return lowest_teleports


if __name__ == "__main__":
    planets = Planets(5)

    print(planets.min_removals())  # 0

    planets.add_teleport(1, 2)
    planets.add_teleport(2, 5)
    print(planets.min_removals())  # 1

    planets.add_teleport(1, 5)
    print(planets.min_removals())  # 2