class Vertex:
    def __init__(self, data):
        self.data = data

    def __repr__(self):  # voor afdrukken
        return str(self.data)

    def __lt__(self, other):  # voor sorteren
        return self.data < other.data


import math

INFINITY = math.inf  # float("inf")


def vertices(G):
    return sorted(G)


def edges(G):
    return [(u, v) for u in vertices(G) for v in G[u]]


# v = [Vertex(i) for i in range(8)]
# G = {v[0]: [v[1], v[4]],
#      v[1]: [v[0], v[5]],
#      v[2]: [v[3], v[5], v[6]],
#      v[3]: [v[2], v[6], v[7]],
#      v[4]: [v[0]],
#      v[5]: [v[1], v[2], v[6]],
#      v[6]: [v[2], v[3], v[5], v[7]],
#      v[7]: [v[3], v[6]]}

v = [Vertex(i) for i in range(9)]
VoorbeeldEdges = {v[0]: [v[4], v[5]],
                  v[1]: [v[4], v[5], v[6]],
                  v[2]: [v[4], v[5], v[6]],
                  v[3]: [v[7]],
                  v[4]: [v[0], v[1], v[5]],
                  v[5]: [v[4], v[0], v[1], v[2]],
                  v[6]: [v[1], v[2]],
                  v[7]: [v[3]],
                  v[8]: []
                  }

# print(VoorbeeldEdges)
# print(VoorbeeldEdges[v[8]])



def is_connected(g, first, last):
    if last in build_predecessors(g, first).keys():
        return True
    else:
        return False


def build_predecessors(g, first):
    prelist = {}
    que = []
    queisNone = False
    current = first
    prelist[first] = None
    while not queisNone:

        for temp in g[current]:
            if temp not in prelist.keys():
                que.append(temp)
                prelist[temp] = current
        if len(que) == 0:
            queisNone = True
        if len(que) != 0:
            current = que.pop(0)
    return prelist


print(is_connected(VoorbeeldEdges, v[4],v[3]))