class Graph:
    """A directed graph, represented as two maps,
    one from each vertex to the set of outbound neighbours,
    the other from each vertex to the set of inbound neighbours"""


    def __init__(self, n ):
        """Creates a graph with n vertices (numbered from 0 to n-1)
        and no edges"""
        self._out = {}
        self._in = {}
        self._cost = {}

        self._costs2 = Cost()

        for i in range(n):
            self._out[i] = []
            self._in[i] = []
          #  self._cost[i] = [0]   #as default


    def parseX(self):
         """Returns an iterable containing all the vertices"""
         return self._out.keys()



    def addEdge(self, x, y, c):
        """Adds an edge from x to y.
        Precondition: there is no edge from x to y

        preconditions: y not already among the neighbours os x

        """
        if y in self._out[x] and x in self._in[y]:
            return
        self._out[x].append(y)
        self._in[y].append(x)
        self._cost[x].append(c)
        self._costs2.addCost(x, y, c)


    def removeEdge(self, x, y):
        """
        Removes an edge from the graph, having the source vertex x and the destination vertex y
        :param x: the source
        :param y: destination
        :return: the graph will be updated with the new actual state
        """
        if x in self._out.keys():
            for yy in self._out[x]:
                if yy == y:
                    self._out[x].remove(y)
                    self._in[y].remove(x)

                    return True
        return False

    def existsVertex(self, x):
        return x in self._in.keys()


    def removeVertex(self, x):
        """
        the function removes the vertex indicated by the input parameter
        :param x: the vertex to be removed
        :return: true if it was removed and false otherwise
        """
        """
        first we will remove x from the outbound edges list
        and then proceed to removing x from all the lists where it is included
        """

        self._out[x] = []  #initialize it with empty list
        self._out.pop(x)
        self._in.pop(x)
        ok = 0
        for a in self._out.keys():
            for b in self._out[a]:
                if b == x:
                    ok = 1
                    self._out[a].remove(x)
                    self._costs2.removeCost(a, b)
            for b in self._in[a]:
                if b == x:
                    ok = 1
                    self._in[a].remove(x)
                    self._costs2.removeCost(a, b)
        if ok == 1:
            return True
        return False

    def isEdge(self,x,y):
        """Returns True if there is an edge from x to y, False otherwise"""
        return y in self._out[x]

    def parseOUT(self,x):
        """Returns an iterable containing the outbound neighbours of x"""
        return self._out[x]

    def parseIN(self,y):
        """Returns an iterable containing the inbound neighbours of x"""
        return self._in[y]


    def printOUT(self):
        """
        prints vertices which have x as source vertex
        """
        for x in self._out:
            print (str(x)+ "-->"+ str(self._out[x]) +"\n")

    def printIN(self):
        """
        prints vertices which have y as destination vertex
        """
        for y in self._in:
            print (str(y)+"<-- "+str(self._in[y])+"\n")

    def getCostVertexes(self, x, y):
        """
        :param x: source vertex
        :param y: destination vertex
        :return: -1 if at least one of the vertexes is not in the dictionaries of the graph, which means that the edge does not exist
        and otherwise returns the cost of the edge determined by the two vertexes
        """
        if x not in self._in.keys() or y not in self._in.keys():
            return -1
        cost = 0
        cost = self._costs2.getCost(x, y)
        return cost

def getfromfile(fname):
    """
    in:n-number of vertices
        m-number of edges
        x-source vertex
        y-destination vertex
        c-cost
    out:created graph with n-verices, m-edges according to x,y,c
    """
    try:
            f=open(fname,"r")

    except IOError:
        raise IOError( "Not enough space")
    line = f.readline().strip()
    t = line.split(" ")
    n = int(t[0])
    m = int(t[1])
    G = Graph(n)
    for i in range(m):
        line = f.readline().strip()
        t = line.split(" ")
        x = int(t[0])
        y = int(t[1])
        c = int(t[2])
        G.addEdge(x,y,c)

    return G


class Cost:
    def __init__(self):
        self._dictionary = {}

    def addCost(self, x, y, cost):
        self._dictionary[(x, y)] = cost

    def getCost(self, x, y):
        if (x, y) in self._dictionary.keys():
            return self._dictionary[(x, y)]
        return 0

    def removeCost(self, x, y):
        """"
        removes the cost corresponging to the tuple (x, y)
        returns true if the operation was performed and false otherwise
        """
        if (x, y) not in self._dictionary.keys():
            return False
        self._dictionary.pop((x, y), None)

def test():
    G = getfromfile("graf.txt")
    print (G.parseX())
    G.printOUT()
    print ("\n")
    G.printIN()

def test2():
    G = Graph(5)
    print( G._cost)