import sys


class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}
        self.distance = sys.maxsize
        self.predecessor = None
        self.color = 'White'
        self.dicoveryTime = 0
        self.finishTime = 0

    def setDistance(self, d):
        self.distance = d

    def getDistance(self):
        return self.distance

    def setPred(self, p):
        self.predecessor = p

    def getPred(self):
        return self.predecessor

    def setColor(self, c):
        self.color = c

    def getColor(self):
        return self.color

    def addNeighbour(self, neighbour, weight=0):
        self.connectedTo[neighbour] = weight

    def __str__(self):
        return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self, neighbour):
        return self.connectedTo[neighbour]

class Graph:
    def __init__(self):
        self.vertexlist = {}
        self.numVertices = 0

    def addVertex(self, key):
        self.numVertices += 1
        newVertex = Vertex(key)
        self.vertexlist[key] = newVertex
        return newVertex

    def getVertex(self, key):
        if key in self.vertexlist:
            return self.vertexlist[key]
        else:
            return None

    def __contains__(self, key):
        return key in self.vertexlist

    def addEdge(self, start, end, weight=0):
        if start not in self.vertexlist:
            newvertex = self.addVertex(start)
        if end not in self.vertexlist:
            newvertex = self.addVertex(end)
        self.vertexlist[start].addNeighbour(self.vertexlist[end], weight)

    def getVerteices(self):
        return self.vertexlist.keys()

    def __iter__(self):
        return iter(self.vertexlist.values())