MST.py

from collections import defaultdict, namedtuple
Arc = namedtuple('Arc', ('tail', 'weight', 'head'))
def spanning_arborescence(arcs, sink,kick):
    l=len(arcs)
    while l>=0:
        x=arcs[l-1]                                          #best incoming edges list traversed in the reverse order in which they were added
        l=l-1
        if x in kick:
           for arc in arcs:
               if arc==kick[x] or arc in kick[x]:
                   i=arcs.index(arc)                  #every edge will kick out one edge inside the merged node, breaking the cycle.
                   arcs[i]=x                          #every edge in the Kick dictionary is removed from the best incoming edge(arcs) list
                          
    return(set(arcs))

def find_cycle(successor, sink):
        visited = {sink}
        for node in successor:
            cycle = []
            while node not in visited:
                visited.add(node)           #keeping a track of the traversed nodes
                cycle.append(node)                                                               
                node = successor[node]      #if the node's parent is present in the list 'cycle',it verifies the presence of a cycle 
            if node in cycle:
                return cycle[cycle.index(node):]
        return None

class MSTT:
    def max_spanning_arborescence(self,arcs, sink): 
        kick={}                                              #dictionary storing the kicked out edges of the arcs
        good_arcs = []                                       #list storing the best (maximum) arc of every node
        quotient_map = {arc.tail: arc.tail for arc in arcs}   #dictionary for tail(key) to tail(value) mapping of every arc
        quotient_map[sink] = sink
        score={arc:arc.weight for arc in arcs}      #score for updating the weights on detecting a cycle 
        while True:
            max_arc_by_tail_rep = {}    #dictionary storing the maximum incoming arc(value) of every node(key)                                                                             
            successor_rep = {}          #dictionary storing the parent node of every node selected in max_arc_by_tail_rep                                                                       
            for arc in arcs:
                if arc.tail == sink:    #avoiding the arcs which have root as their tail
                    continue
                tail_rep = quotient_map[arc.tail]
                head_rep = quotient_map[arc.head]
                if tail_rep == head_rep:                 #avoiding the self loops 
                    continue
                if tail_rep not in max_arc_by_tail_rep or score[max_arc_by_tail_rep[tail_rep]] < score[arc]:    
                    max_arc_by_tail_rep[tail_rep] = arc         #selecting the maximum incoming arc for every node                                                       
                    successor_rep[tail_rep] = head_rep
            
            cycle_reps = find_cycle(successor_rep, sink)            
            if cycle_reps is None:                                 #Repeated until every non-root node has an incoming edge and no cycles are formed                    
                 z=[]                                               
                 z.extend(max_arc_by_tail_rep.values())             
                 while z:
                     y=z.pop(0)
                     good_arcs.append(y) if y not in good_arcs else None         
                 return spanning_arborescence(good_arcs, sink,kick)
            for arc in arcs:
                tail_rep = quotient_map[arc.tail]
                head_rep = quotient_map[arc.head]
                if arc.tail == sink:
                    continue
                if tail_rep == head_rep:
                    continue
                if tail_rep in cycle_reps and arc!= max_arc_by_tail_rep[tail_rep] and head_rep not in cycle_reps:
                    score[arc]=score[arc]-score[max_arc_by_tail_rep[tail_rep]]                                      #updating the score of the incoming edges whose tails form a cycle
                    y=kick.get(arc)
                    if y is not None:
                        kick.setdefault(arc,[]).append(max_arc_by_tail_rep[tail_rep])                               #adding the best incoming arc as the kicked out edges of every incoming arc whose score was updated
                    else:
                        kick.setdefault(arc,[]).append(max_arc_by_tail_rep[tail_rep])
            z=[]
            z.extend(max_arc_by_tail_rep.values())
            while z:
                y=z.pop(0)
                good_arcs.append(y) if y not in good_arcs else None                                                 #Adding the best incoming arc of every merged and unmerged nodes of the graph
            cycle_rep_set = set(cycle_reps)
            cycle_rep = cycle_rep_set.pop()
            quotient_map = {node: cycle_rep if node_rep in cycle_rep_set else node_rep for node, node_rep in quotient_map.items()}    #contracting the nodes in cycle_reps
            
    def min_spanning_arborescence(self,arcs, sink): 
        kick={}                                              #dictionary storing the kicked out edges of the arcs
        good_arcs = []                                       #list storing the best (minimum) arc of every node
        quotient_map = {arc.tail: arc.tail for arc in arcs}   #dictionary for tail(key) to tail(value) mapping of every arc
        quotient_map[sink] = sink
        score={arc:arc.weight for arc in arcs}      #score for updating the weights on detecting a cycle 
        while True:
            min_arc_by_tail_rep = {}    #dictionary storing the minimum incoming arc(value) of every node(key)                                                                             
            successor_rep = {}          #dictionary storing the parent node of every node selected in max_arc_by_tail_rep                                                                       
            for arc in arcs:
                if arc.tail == sink:    #avoiding the arcs which have root as their tail
                    continue
                tail_rep = quotient_map[arc.tail]
                head_rep = quotient_map[arc.head]
                if tail_rep == head_rep:                 #avoiding the self loops 
                    continue
                if tail_rep not in min_arc_by_tail_rep or score[min_arc_by_tail_rep[tail_rep]] > score[arc]:    
                    min_arc_by_tail_rep[tail_rep] = arc         #selecting the maximum incoming arc for every node                                                       
                    successor_rep[tail_rep] = head_rep
            
            cycle_reps = find_cycle(successor_rep, sink)            
            if cycle_reps is None:                                 #Repeated until every non-root node has an incoming edge and no cycles are formed                    
                 z=[]                                               
                 z.extend(min_arc_by_tail_rep.values())             
                 while z:
                     y=z.pop(0)
                     good_arcs.append(y) if y not in good_arcs else None         
                 return spanning_arborescence(good_arcs, sink,kick)
            for arc in arcs:
                tail_rep = quotient_map[arc.tail]
                head_rep = quotient_map[arc.head]
                if arc.tail == sink:
                    continue
                if tail_rep == head_rep:
                    continue
                if tail_rep in cycle_reps and arc!= min_arc_by_tail_rep[tail_rep] and head_rep not in cycle_reps:
                    score[arc]=score[arc]-score[min_arc_by_tail_rep[tail_rep]]                                      #updating the score of the incoming edges whose tails form a cycle
                    y=kick.get(arc)
                    if y is not None:
                        kick.setdefault(arc,[]).append(min_arc_by_tail_rep[tail_rep])                               #adding the best incoming arc as the kicked out edges of every incoming arc whose score was updated
                    else:
                        kick.setdefault(arc,[]).append(min_arc_by_tail_rep[tail_rep])
            z=[]
            z.extend(min_arc_by_tail_rep.values())
            while z:
                y=z.pop(0)
                good_arcs.append(y) if y not in good_arcs else None                                                 #Adding the best incoming arc of every merged and unmerged nodes of the graph
            cycle_rep_set = set(cycle_reps)
            cycle_rep = cycle_rep_set.pop()
            quotient_map = {node: cycle_rep if node_rep in cycle_rep_set else node_rep for node, node_rep in quotient_map.items()}    #contracting the nodes in cycle_reps
                                                                                                          
            
#l={}       
#m=MSTT()
#l=m.max_spanning_arborescence([Arc(tail=2, weight=25, head=1), Arc(tail=3, weight=-24, head=1), Arc(tail=4, weight=17, head=1), Arc(tail=5, weight=-24, head=1), Arc(tail=6, weight=25, head=1), Arc(tail=7, weight=16, head=1), Arc(tail=8, weight=-10, head=1), Arc(tail=9, weight=-11, head=1), Arc(tail=10, weight=-14, head=1), Arc(tail=1, weight=18, head=2), Arc(tail=3, weight=5, head=2), Arc(tail=4, weight=-14, head=2), Arc(tail=5, weight=12, head=2), Arc(tail=6, weight=-1, head=2), Arc(tail=7, weight=23, head=2), Arc(tail=8, weight=4, head=2), Arc(tail=9, weight=-1, head=2), Arc(tail=10, weight=-2, head=2), Arc(tail=1, weight=14, head=3), Arc(tail=2, weight=-4, head=3), Arc(tail=4, weight=-10, head=3), Arc(tail=5, weight=-15, head=3), Arc(tail=6, weight=-16, head=3), Arc(tail=7, weight=-14, head=3), Arc(tail=8, weight=12, head=3), Arc(tail=9, weight=2, head=3), Arc(tail=10, weight=-14, head=3), Arc(tail=1, weight=-17, head=4), Arc(tail=2, weight=13, head=4), Arc(tail=3, weight=13, head=4), Arc(tail=5, weight=-21, head=4), Arc(tail=6, weight=25, head=4), Arc(tail=7, weight=17, head=4), Arc(tail=8, weight=12, head=4), Arc(tail=9, weight=-18, head=4), Arc(tail=10, weight=-11, head=4), Arc(tail=1, weight=9, head=5), Arc(tail=2, weight=-11, head=5), Arc(tail=3, weight=-21, head=5), Arc(tail=4, weight=-22, head=5), Arc(tail=6, weight=-2, head=5), Arc(tail=7, weight=6, head=5), Arc(tail=8, weight=7, head=5), Arc(tail=9, weight=-24, head=5), Arc(tail=10, weight=1, head=5), Arc(tail=1, weight=-1, head=6), Arc(tail=2, weight=24, head=6), Arc(tail=3, weight=-5, head=6), Arc(tail=4, weight=-7, head=6), Arc(tail=5, weight=10, head=6), Arc(tail=7, weight=25, head=6), Arc(tail=8, weight=19, head=6), Arc(tail=9, weight=-4, head=6), Arc(tail=10, weight=-22, head=6), Arc(tail=1, weight=22, head=7), Arc(tail=2, weight=-15, head=7), Arc(tail=3, weight=-13, head=7), Arc(tail=4, weight=18, head=7), Arc(tail=5, weight=-21, head=7), Arc(tail=6, weight=-7, head=7), Arc(tail=8, weight=25, head=7), Arc(tail=9, weight=-22, head=7), Arc(tail=10, weight=-8, head=7), Arc(tail=1, weight=15, head=8), Arc(tail=2, weight=21, head=8), Arc(tail=3, weight=3, head=8), Arc(tail=4, weight=-5, head=8), Arc(tail=5, weight=14, head=8), Arc(tail=6, weight=21, head=8), Arc(tail=7, weight=0, head=8), Arc(tail=9, weight=-13, head=8), Arc(tail=10, weight=11, head=8), Arc(tail=1, weight=16, head=9), Arc(tail=2, weight=-4, head=9), Arc(tail=3, weight=8, head=9), Arc(tail=4, weight=14, head=9), Arc(tail=5, weight=-5, head=9), Arc(tail=6, weight=16, head=9), Arc(tail=7, weight=-23, head=9), Arc(tail=8, weight=24, head=9), Arc(tail=10, weight=1, head=9), Arc(tail=1, weight=8, head=10), Arc(tail=2, weight=19, head=10), Arc(tail=3, weight=3, head=10), Arc(tail=4, weight=-19, head=10), Arc(tail=5, weight=22, head=10), Arc(tail=6, weight=-12, head=10), Arc(tail=7, weight=0, head=10), Arc(tail=8, weight=24, head=10), Arc(tail=9, weight=-14, head=10)],9)            
#l=m.min_spanning_arborescence([Arc(tail=2, weight=5, head=1), Arc(tail=3, weight=-10, head=1), Arc(tail=4, weight=25, head=1), Arc(tail=5, weight=13, head=1), Arc(tail=6, weight=-12, head=1), Arc(tail=7, weight=10, head=1), Arc(tail=8, weight=20, head=1), Arc(tail=9, weight=-16, head=1), Arc(tail=10, weight=-2, head=1), Arc(tail=11, weight=25, head=1), Arc(tail=12, weight=24, head=1), Arc(tail=13, weight=-17, head=1), Arc(tail=14, weight=8, head=1), Arc(tail=15, weight=-5, head=1), Arc(tail=16, weight=-22, head=1), Arc(tail=17, weight=-20, head=1), Arc(tail=18, weight=-4, head=1), Arc(tail=20, weight=-9, head=1), Arc(tail=22, weight=-12, head=1), Arc(tail=23, weight=9, head=1), Arc(tail=24, weight=4, head=1), Arc(tail=25, weight=-2, head=1), Arc(tail=26, weight=-14, head=1), Arc(tail=27, weight=-20, head=1), Arc(tail=28, weight=-10, head=1), Arc(tail=29, weight=-23, head=1), Arc(tail=30, weight=11, head=1), Arc(tail=31, weight=16, head=1), Arc(tail=32, weight=16, head=1), Arc(tail=33, weight=23, head=1), Arc(tail=34, weight=-15, head=1), Arc(tail=35, weight=-20, head=1), Arc(tail=36, weight=-23, head=1), Arc(tail=37, weight=-17, head=1), Arc(tail=1, weight=-16, head=2), Arc(tail=3, weight=-10, head=2), Arc(tail=4, weight=-25, head=2), Arc(tail=5, weight=-12, head=2), Arc(tail=6, weight=-18, head=2), Arc(tail=7, weight=10, head=2), Arc(tail=8, weight=-16, head=2), Arc(tail=9, weight=16, head=2), Arc(tail=10, weight=9, head=2), Arc(tail=11, weight=13, head=2), Arc(tail=12, weight=22, head=2), Arc(tail=13, weight=7, head=2), Arc(tail=14, weight=24, head=2), Arc(tail=15, weight=2, head=2), Arc(tail=16, weight=-15, head=2), Arc(tail=17, weight=24, head=2), Arc(tail=18, weight=8, head=2), Arc(tail=20, weight=24, head=2), Arc(tail=22, weight=4, head=2), Arc(tail=23, weight=8, head=2), Arc(tail=24, weight=16, head=2), Arc(tail=25, weight=5, head=2), Arc(tail=26, weight=8, head=2), Arc(tail=27, weight=22, head=2), Arc(tail=28, weight=3, head=2), Arc(tail=29, weight=-7, head=2), Arc(tail=30, weight=3, head=2), Arc(tail=31, weight=4, head=2), Arc(tail=32, weight=-14, head=2), Arc(tail=33, weight=19, head=2), Arc(tail=34, weight=10, head=2), Arc(tail=35, weight=21, head=2), Arc(tail=36, weight=-3, head=2), Arc(tail=37, weight=21, head=2), Arc(tail=1, weight=-20, head=3), Arc(tail=2, weight=-6, head=3), Arc(tail=4, weight=-9, head=3), Arc(tail=5, weight=-10, head=3), Arc(tail=6, weight=-19, head=3), Arc(tail=7, weight=-5, head=3), Arc(tail=8, weight=0, head=3), Arc(tail=9, weight=-10, head=3), Arc(tail=10, weight=16, head=3), Arc(tail=11, weight=13, head=3), Arc(tail=12, weight=2, head=3), Arc(tail=13, weight=-21, head=3), Arc(tail=14, weight=-2, head=3), Arc(tail=15, weight=3, head=3), Arc(tail=16, weight=-1, head=3), Arc(tail=17, weight=-7, head=3), Arc(tail=18, weight=-4, head=3), Arc(tail=20, weight=0, head=3), Arc(tail=22, weight=11, head=3), Arc(tail=23, weight=-16, head=3), Arc(tail=24, weight=-4, head=3), Arc(tail=25, weight=-4, head=3), Arc(tail=26, weight=4, head=3), Arc(tail=27, weight=23, head=3), Arc(tail=28, weight=2, head=3), Arc(tail=29, weight=-15, head=3), Arc(tail=30, weight=-13, head=3), Arc(tail=31, weight=-12, head=3), Arc(tail=32, weight=15, head=3), Arc(tail=33, weight=10, head=3), Arc(tail=34, weight=20, head=3), Arc(tail=35, weight=6, head=3), Arc(tail=36, weight=18, head=3), Arc(tail=37, weight=11, head=3), Arc(tail=1, weight=18, head=4), Arc(tail=2, weight=13, head=4), Arc(tail=3, weight=17, head=4), Arc(tail=5, weight=3, head=4), Arc(tail=6, weight=-18, head=4), Arc(tail=7, weight=-5, head=4), Arc(tail=8, weight=-19, head=4), Arc(tail=9, weight=14, head=4), Arc(tail=10, weight=-20, head=4), Arc(tail=11, weight=13, head=4), Arc(tail=12, weight=12, head=4), Arc(tail=13, weight=-15, head=4), Arc(tail=14, weight=-6, head=4), Arc(tail=15, weight=8, head=4), Arc(tail=16, weight=22, head=4), Arc(tail=17, weight=-5, head=4), Arc(tail=18, weight=-11, head=4), Arc(tail=20, weight=-9, head=4), Arc(tail=22, weight=-25, head=4), Arc(tail=23, weight=-9, head=4), Arc(tail=24, weight=-16, head=4), Arc(tail=25, weight=14, head=4), Arc(tail=26, weight=-10, head=4), Arc(tail=27, weight=-13, head=4), Arc(tail=28, weight=7, head=4), Arc(tail=29, weight=-20, head=4), Arc(tail=30, weight=-9, head=4), Arc(tail=31, weight=16, head=4), Arc(tail=32, weight=-16, head=4), Arc(tail=33, weight=22, head=4), Arc(tail=34, weight=-5, head=4), Arc(tail=35, weight=-25, head=4), Arc(tail=36, weight=-20, head=4), Arc(tail=37, weight=1, head=4), Arc(tail=1, weight=9, head=5), Arc(tail=2, weight=11, head=5), Arc(tail=3, weight=22, head=5), Arc(tail=4, weight=-17, head=5), Arc(tail=6, weight=19, head=5), Arc(tail=7, weight=-20, head=5), Arc(tail=8, weight=18, head=5), Arc(tail=9, weight=20, head=5), Arc(tail=10, weight=2, head=5), Arc(tail=11, weight=-8, head=5), Arc(tail=12, weight=-13, head=5), Arc(tail=13, weight=-24, head=5), Arc(tail=14, weight=20, head=5), Arc(tail=15, weight=19, head=5), Arc(tail=16, weight=10, head=5), Arc(tail=17, weight=-2, head=5), Arc(tail=18, weight=11, head=5), Arc(tail=20, weight=15, head=5), Arc(tail=22, weight=25, head=5), Arc(tail=23, weight=0, head=5), Arc(tail=24, weight=-22, head=5), Arc(tail=25, weight=5, head=5), Arc(tail=26, weight=13, head=5), Arc(tail=27, weight=-13, head=5), Arc(tail=28, weight=-4, head=5), Arc(tail=29, weight=-16, head=5), Arc(tail=30, weight=13, head=5), Arc(tail=31, weight=-17, head=5), Arc(tail=32, weight=-16, head=5), Arc(tail=33, weight=22, head=5), Arc(tail=34, weight=-22, head=5), Arc(tail=35, weight=-21, head=5), Arc(tail=36, weight=-6, head=5), Arc(tail=37, weight=-15, head=5), Arc(tail=1, weight=20, head=6), Arc(tail=2, weight=-17, head=6), Arc(tail=3, weight=24, head=6), Arc(tail=4, weight=-15, head=6), Arc(tail=5, weight=0, head=6), Arc(tail=7, weight=3, head=6), Arc(tail=8, weight=-8, head=6), Arc(tail=9, weight=-21, head=6), Arc(tail=10, weight=-1, head=6), Arc(tail=11, weight=-25, head=6), Arc(tail=12, weight=12, head=6), Arc(tail=13, weight=21, head=6), Arc(tail=14, weight=-11, head=6), Arc(tail=15, weight=-13, head=6), Arc(tail=16, weight=-9, head=6), Arc(tail=17, weight=-19, head=6), Arc(tail=18, weight=-2, head=6), Arc(tail=20, weight=-4, head=6), Arc(tail=22, weight=24, head=6), Arc(tail=23, weight=-17, head=6), Arc(tail=24, weight=25, head=6), Arc(tail=25, weight=17, head=6), Arc(tail=26, weight=-11, head=6), Arc(tail=27, weight=8, head=6), Arc(tail=28, weight=-22, head=6), Arc(tail=29, weight=-13, head=6), Arc(tail=30, weight=-17, head=6), Arc(tail=31, weight=22, head=6), Arc(tail=32, weight=-2, head=6), Arc(tail=33, weight=6, head=6), Arc(tail=34, weight=-15, head=6), Arc(tail=35, weight=15, head=6), Arc(tail=36, weight=-4, head=6), Arc(tail=37, weight=22, head=6), Arc(tail=1, weight=15, head=7), Arc(tail=2, weight=-5, head=7), Arc(tail=3, weight=-15, head=7), Arc(tail=4, weight=11, head=7), Arc(tail=5, weight=-13, head=7), Arc(tail=6, weight=-24, head=7), Arc(tail=8, weight=-5, head=7), Arc(tail=9, weight=-17, head=7), Arc(tail=10, weight=-16, head=7), Arc(tail=11, weight=-9, head=7), Arc(tail=12, weight=3, head=7), Arc(tail=13, weight=20, head=7), Arc(tail=14, weight=22, head=7), Arc(tail=15, weight=11, head=7), Arc(tail=16, weight=-3, head=7), Arc(tail=17, weight=7, head=7), Arc(tail=18, weight=-18, head=7), Arc(tail=20, weight=-6, head=7), Arc(tail=22, weight=-19, head=7), Arc(tail=23, weight=-11, head=7), Arc(tail=24, weight=-23, head=7), Arc(tail=25, weight=-4, head=7), Arc(tail=26, weight=10, head=7), Arc(tail=27, weight=21, head=7), Arc(tail=28, weight=-20, head=7), Arc(tail=29, weight=0, head=7), Arc(tail=30, weight=12, head=7), Arc(tail=31, weight=5, head=7), Arc(tail=32, weight=-13, head=7), Arc(tail=33, weight=9, head=7), Arc(tail=34, weight=-7, head=7), Arc(tail=35, weight=12, head=7), Arc(tail=36, weight=18, head=7), Arc(tail=37, weight=25, head=7), Arc(tail=1, weight=14, head=8), Arc(tail=2, weight=-13, head=8), Arc(tail=3, weight=-22, head=8), Arc(tail=4, weight=-2, head=8), Arc(tail=5, weight=-21, head=8), Arc(tail=6, weight=-6, head=8), Arc(tail=7, weight=12, head=8), Arc(tail=9, weight=-23, head=8), Arc(tail=10, weight=-8, head=8), Arc(tail=11, weight=19, head=8), Arc(tail=12, weight=24, head=8), Arc(tail=13, weight=11, head=8), Arc(tail=14, weight=-18, head=8), Arc(tail=15, weight=-9, head=8), Arc(tail=16, weight=-3, head=8), Arc(tail=17, weight=15, head=8), Arc(tail=18, weight=3, head=8), Arc(tail=20, weight=-17, head=8), Arc(tail=22, weight=20, head=8), Arc(tail=23, weight=-23, head=8), Arc(tail=24, weight=-5, head=8), Arc(tail=25, weight=-10, head=8), Arc(tail=26, weight=-10, head=8), Arc(tail=27, weight=-5, head=8), Arc(tail=28, weight=9, head=8), Arc(tail=29, weight=5, head=8), Arc(tail=30, weight=18, head=8), Arc(tail=31, weight=3, head=8), Arc(tail=32, weight=-20, head=8), Arc(tail=33, weight=-11, head=8), Arc(tail=34, weight=-12, head=8), Arc(tail=35, weight=11, head=8), Arc(tail=36, weight=10, head=8), Arc(tail=37, weight=22, head=8), Arc(tail=1, weight=-2, head=9), Arc(tail=2, weight=-25, head=9), Arc(tail=3, weight=-10, head=9), Arc(tail=4, weight=-6, head=9), Arc(tail=5, weight=-25, head=9), Arc(tail=6, weight=10, head=9), Arc(tail=7, weight=-21, head=9), Arc(tail=8, weight=-6, head=9), Arc(tail=10, weight=-6, head=9), Arc(tail=11, weight=6, head=9), Arc(tail=12, weight=3, head=9), Arc(tail=13, weight=14, head=9), Arc(tail=14, weight=-2, head=9), Arc(tail=15, weight=-18, head=9), Arc(tail=16, weight=20, head=9), Arc(tail=17, weight=17, head=9), Arc(tail=18, weight=-11, head=9), Arc(tail=20, weight=22, head=9), Arc(tail=22, weight=13, head=9), Arc(tail=23, weight=-1, head=9), Arc(tail=24, weight=-12, head=9), Arc(tail=25, weight=2, head=9), Arc(tail=26, weight=6, head=9), Arc(tail=27, weight=1, head=9), Arc(tail=28, weight=25, head=9), Arc(tail=29, weight=1, head=9), Arc(tail=30, weight=1, head=9), Arc(tail=31, weight=-10, head=9), Arc(tail=32, weight=-2, head=9), Arc(tail=33, weight=-4, head=9), Arc(tail=34, weight=1, head=9), Arc(tail=35, weight=16, head=9), Arc(tail=36, weight=-14, head=9), Arc(tail=37, weight=-3, head=9), Arc(tail=1, weight=3, head=10), Arc(tail=2, weight=12, head=10), Arc(tail=3, weight=22, head=10), Arc(tail=4, weight=-6, head=10), Arc(tail=5, weight=2, head=10), Arc(tail=6, weight=-9, head=10), Arc(tail=7, weight=7, head=10), Arc(tail=8, weight=1, head=10), Arc(tail=9, weight=-12, head=10), Arc(tail=11, weight=19, head=10), Arc(tail=12, weight=-15, head=10), Arc(tail=13, weight=-20, head=10), Arc(tail=14, weight=-15, head=10), Arc(tail=15, weight=-22, head=10), Arc(tail=16, weight=8, head=10), Arc(tail=17, weight=-24, head=10), Arc(tail=18, weight=-1, head=10), Arc(tail=20, weight=25, head=10), Arc(tail=22, weight=-3, head=10), Arc(tail=23, weight=-2, head=10), Arc(tail=24, weight=-18, head=10), Arc(tail=25, weight=-24, head=10), Arc(tail=26, weight=-11, head=10), Arc(tail=27, weight=-7, head=10), Arc(tail=28, weight=7, head=10), Arc(tail=29, weight=2, head=10), Arc(tail=30, weight=21, head=10), Arc(tail=31, weight=16, head=10), Arc(tail=32, weight=-22, head=10), Arc(tail=33, weight=-7, head=10), Arc(tail=34, weight=-8, head=10), Arc(tail=35, weight=-23, head=10), Arc(tail=36, weight=-11, head=10), Arc(tail=37, weight=10, head=10), Arc(tail=1, weight=18, head=11), Arc(tail=2, weight=-10, head=11), Arc(tail=3, weight=15, head=11), Arc(tail=4, weight=16, head=11), Arc(tail=5, weight=15, head=11), Arc(tail=6, weight=18, head=11), Arc(tail=7, weight=-16, head=11), Arc(tail=8, weight=22, head=11), Arc(tail=9, weight=0, head=11), Arc(tail=10, weight=-8, head=11), Arc(tail=12, weight=1, head=11), Arc(tail=13, weight=8, head=11), Arc(tail=14, weight=-4, head=11), Arc(tail=15, weight=9, head=11), Arc(tail=16, weight=-23, head=11), Arc(tail=17, weight=-15, head=11), Arc(tail=18, weight=-3, head=11), Arc(tail=20, weight=-1, head=11), Arc(tail=22, weight=18, head=11), Arc(tail=23, weight=18, head=11), Arc(tail=24, weight=10, head=11), Arc(tail=25, weight=16, head=11), Arc(tail=26, weight=1, head=11), Arc(tail=27, weight=-12, head=11), Arc(tail=28, weight=-25, head=11), Arc(tail=29, weight=20, head=11), Arc(tail=30, weight=0, head=11), Arc(tail=31, weight=16, head=11), Arc(tail=32, weight=-14, head=11), Arc(tail=33, weight=-17, head=11), Arc(tail=34, weight=2, head=11), Arc(tail=35, weight=-7, head=11), Arc(tail=36, weight=-15, head=11), Arc(tail=37, weight=-12, head=11), Arc(tail=1, weight=15, head=12), Arc(tail=2, weight=10, head=12), Arc(tail=3, weight=-3, head=12), Arc(tail=4, weight=20, head=12), Arc(tail=5, weight=-5, head=12), Arc(tail=6, weight=-14, head=12), Arc(tail=7, weight=-18, head=12), Arc(tail=8, weight=13, head=12), Arc(tail=9, weight=25, head=12), Arc(tail=10, weight=1, head=12), Arc(tail=11, weight=-24, head=12), Arc(tail=13, weight=-25, head=12), Arc(tail=14, weight=-12, head=12), Arc(tail=15, weight=-7, head=12), Arc(tail=16, weight=5, head=12), Arc(tail=17, weight=-1, head=12), Arc(tail=18, weight=-5, head=12), Arc(tail=20, weight=0, head=12), Arc(tail=22, weight=-25, head=12), Arc(tail=23, weight=-14, head=12), Arc(tail=24, weight=16, head=12), Arc(tail=25, weight=-10, head=12), Arc(tail=26, weight=-2, head=12), Arc(tail=27, weight=5, head=12), Arc(tail=28, weight=-25, head=12), Arc(tail=29, weight=0, head=12), Arc(tail=30, weight=-15, head=12), Arc(tail=31, weight=3, head=12), Arc(tail=32, weight=-7, head=12), Arc(tail=33, weight=-18, head=12), Arc(tail=34, weight=15, head=12), Arc(tail=35, weight=-6, head=12), Arc(tail=36, weight=-15, head=12), Arc(tail=37, weight=-24, head=12), Arc(tail=1, weight=-16, head=13), Arc(tail=2, weight=-21, head=13), Arc(tail=3, weight=-18, head=13), Arc(tail=4, weight=-16, head=13), Arc(tail=5, weight=-8, head=13), Arc(tail=6, weight=3, head=13), Arc(tail=7, weight=4, head=13), Arc(tail=8, weight=0, head=13), Arc(tail=9, weight=20, head=13), Arc(tail=10, weight=8, head=13), Arc(tail=11, weight=10, head=13), Arc(tail=12, weight=-23, head=13), Arc(tail=14, weight=-23, head=13), Arc(tail=15, weight=24, head=13), Arc(tail=16, weight=19, head=13), Arc(tail=17, weight=-24, head=13), Arc(tail=18, weight=12, head=13), Arc(tail=20, weight=6, head=13), Arc(tail=22, weight=9, head=13), Arc(tail=23, weight=-12, head=13), Arc(tail=24, weight=8, head=13), Arc(tail=25, weight=16, head=13), Arc(tail=26, weight=1, head=13), Arc(tail=27, weight=-21, head=13), Arc(tail=28, weight=-21, head=13), Arc(tail=29, weight=5, head=13), Arc(tail=30, weight=-2, head=13), Arc(tail=31, weight=-19, head=13), Arc(tail=32, weight=8, head=13), Arc(tail=33, weight=20, head=13), Arc(tail=34, weight=15, head=13), Arc(tail=35, weight=-1, head=13), Arc(tail=36, weight=-10, head=13), Arc(tail=37, weight=12, head=13), Arc(tail=1, weight=14, head=14), Arc(tail=2, weight=-1, head=14), Arc(tail=3, weight=6, head=14), Arc(tail=4, weight=-21, head=14), Arc(tail=5, weight=-5, head=14), Arc(tail=6, weight=-10, head=14), Arc(tail=7, weight=15, head=14), Arc(tail=8, weight=13, head=14), Arc(tail=9, weight=10, head=14), Arc(tail=10, weight=4, head=14), Arc(tail=11, weight=-3, head=14), Arc(tail=12, weight=-23, head=14), Arc(tail=13, weight=-20, head=14), Arc(tail=15, weight=-18, head=14), Arc(tail=16, weight=1, head=14), Arc(tail=17, weight=12, head=14), Arc(tail=18, weight=1, head=14), Arc(tail=20, weight=-23, head=14), Arc(tail=22, weight=-5, head=14), Arc(tail=23, weight=6, head=14), Arc(tail=24, weight=5, head=14), Arc(tail=25, weight=-1, head=14), Arc(tail=26, weight=3, head=14), Arc(tail=27, weight=12, head=14), Arc(tail=28, weight=-19, head=14), Arc(tail=29, weight=-15, head=14), Arc(tail=30, weight=-15, head=14), Arc(tail=31, weight=19, head=14), Arc(tail=32, weight=1, head=14), Arc(tail=33, weight=1, head=14), Arc(tail=34, weight=9, head=14), Arc(tail=35, weight=-20, head=14), Arc(tail=36, weight=18, head=14), Arc(tail=37, weight=-4, head=14), Arc(tail=1, weight=-24, head=15), Arc(tail=2, weight=-16, head=15), Arc(tail=3, weight=12, head=15), Arc(tail=4, weight=5, head=15), Arc(tail=5, weight=2, head=15), Arc(tail=6, weight=3, head=15), Arc(tail=7, weight=-16, head=15), Arc(tail=8, weight=-20, head=15), Arc(tail=9, weight=-3, head=15), Arc(tail=10, weight=23, head=15), Arc(tail=11, weight=12, head=15), Arc(tail=12, weight=12, head=15), Arc(tail=13, weight=11, head=15), Arc(tail=14, weight=-9, head=15), Arc(tail=16, weight=21, head=15), Arc(tail=17, weight=4, head=15), Arc(tail=18, weight=-1, head=15), Arc(tail=20, weight=-10, head=15), Arc(tail=22, weight=3, head=15), Arc(tail=23, weight=-3, head=15), Arc(tail=24, weight=9, head=15), Arc(tail=25, weight=13, head=15), Arc(tail=26, weight=-7, head=15), Arc(tail=27, weight=7, head=15), Arc(tail=28, weight=14, head=15), Arc(tail=29, weight=8, head=15), Arc(tail=30, weight=-19, head=15), Arc(tail=31, weight=3, head=15), Arc(tail=32, weight=18, head=15), Arc(tail=33, weight=-11, head=15), Arc(tail=34, weight=2, head=15), Arc(tail=35, weight=-25, head=15), Arc(tail=36, weight=12, head=15), Arc(tail=37, weight=-18, head=15), Arc(tail=1, weight=-20, head=16), Arc(tail=2, weight=21, head=16), Arc(tail=3, weight=6, head=16), Arc(tail=4, weight=-10, head=16), Arc(tail=5, weight=19, head=16), Arc(tail=6, weight=10, head=16), Arc(tail=7, weight=-24, head=16), Arc(tail=8, weight=10, head=16), Arc(tail=9, weight=7, head=16), Arc(tail=10, weight=-5, head=16), Arc(tail=11, weight=17, head=16), Arc(tail=12, weight=-9, head=16), Arc(tail=13, weight=20, head=16), Arc(tail=14, weight=24, head=16), Arc(tail=15, weight=-15, head=16), Arc(tail=17, weight=10, head=16), Arc(tail=18, weight=0, head=16), Arc(tail=20, weight=20, head=16), Arc(tail=22, weight=17, head=16), Arc(tail=23, weight=22, head=16), Arc(tail=24, weight=24, head=16), Arc(tail=25, weight=3, head=16), Arc(tail=26, weight=0, head=16), Arc(tail=27, weight=10, head=16), Arc(tail=28, weight=19, head=16), Arc(tail=29, weight=23, head=16), Arc(tail=30, weight=18, head=16), Arc(tail=31, weight=6, head=16), Arc(tail=32, weight=2, head=16), Arc(tail=33, weight=-12, head=16), Arc(tail=34, weight=-1, head=16), Arc(tail=35, weight=6, head=16), Arc(tail=36, weight=14, head=16), Arc(tail=37, weight=13, head=16), Arc(tail=1, weight=3, head=17), Arc(tail=2, weight=17, head=17), Arc(tail=3, weight=8, head=17), Arc(tail=4, weight=16, head=17), Arc(tail=5, weight=9, head=17), Arc(tail=6, weight=-1, head=17), Arc(tail=7, weight=-21, head=17), Arc(tail=8, weight=-8, head=17), Arc(tail=9, weight=23, head=17), Arc(tail=10, weight=-5, head=17), Arc(tail=11, weight=11, head=17), Arc(tail=12, weight=24, head=17), Arc(tail=13, weight=21, head=17), Arc(tail=14, weight=-14, head=17), Arc(tail=15, weight=-15, head=17), Arc(tail=16, weight=-9, head=17), Arc(tail=18, weight=-4, head=17), Arc(tail=20, weight=-11, head=17), Arc(tail=22, weight=-2, head=17), Arc(tail=23, weight=-14, head=17), Arc(tail=24, weight=19, head=17), Arc(tail=25, weight=-23, head=17), Arc(tail=26, weight=12, head=17), Arc(tail=27, weight=6, head=17), Arc(tail=28, weight=14, head=17), Arc(tail=29, weight=-13, head=17), Arc(tail=30, weight=-6, head=17), Arc(tail=31, weight=5, head=17), Arc(tail=32, weight=-19, head=17), Arc(tail=33, weight=15, head=17), Arc(tail=34, weight=2, head=17), Arc(tail=35, weight=-17, head=17), Arc(tail=36, weight=4, head=17), Arc(tail=37, weight=-16, head=17), Arc(tail=1, weight=14, head=18), Arc(tail=2, weight=-7, head=18), Arc(tail=3, weight=-15, head=18), Arc(tail=4, weight=-3, head=18), Arc(tail=5, weight=0, head=18), Arc(tail=6, weight=-25, head=18), Arc(tail=7, weight=-8, head=18), Arc(tail=8, weight=4, head=18), Arc(tail=9, weight=11, head=18), Arc(tail=10, weight=16, head=18), Arc(tail=11, weight=9, head=18), Arc(tail=12, weight=-24, head=18), Arc(tail=13, weight=11, head=18), Arc(tail=14, weight=18, head=18), Arc(tail=15, weight=23, head=18), Arc(tail=16, weight=15, head=18), Arc(tail=17, weight=0, head=18), Arc(tail=20, weight=-15, head=18), Arc(tail=22, weight=4, head=18), Arc(tail=23, weight=-12, head=18), Arc(tail=24, weight=5, head=18), Arc(tail=25, weight=-14, head=18), Arc(tail=26, weight=25, head=18), Arc(tail=27, weight=5, head=18), Arc(tail=28, weight=5, head=18), Arc(tail=29, weight=-3, head=18), Arc(tail=30, weight=8, head=18), Arc(tail=31, weight=-25, head=18), Arc(tail=32, weight=11, head=18), Arc(tail=33, weight=-23, head=18), Arc(tail=34, weight=-18, head=18), Arc(tail=35, weight=10, head=18), Arc(tail=36, weight=13, head=18), Arc(tail=37, weight=15, head=18), Arc(tail=17, weight=-18, head=19), Arc(tail=18, weight=7, head=19), Arc(tail=1, weight=-12, head=20), Arc(tail=2, weight=-2, head=20), Arc(tail=3, weight=-15, head=20), Arc(tail=4, weight=7, head=20), Arc(tail=5, weight=17, head=20), Arc(tail=6, weight=-25, head=20), Arc(tail=7, weight=-22, head=20), Arc(tail=8, weight=-12, head=20), Arc(tail=9, weight=-7, head=20), Arc(tail=10, weight=-7, head=20), Arc(tail=11, weight=-14, head=20), Arc(tail=12, weight=2, head=20), Arc(tail=13, weight=-18, head=20), Arc(tail=14, weight=4, head=20), Arc(tail=15, weight=14, head=20), Arc(tail=16, weight=9, head=20), Arc(tail=17, weight=19, head=20), Arc(tail=18, weight=6, head=20), Arc(tail=22, weight=21, head=20), Arc(tail=23, weight=-15, head=20), Arc(tail=24, weight=4, head=20), Arc(tail=25, weight=-10, head=20), Arc(tail=26, weight=-25, head=20), Arc(tail=27, weight=2, head=20), Arc(tail=28, weight=6, head=20), Arc(tail=29, weight=-19, head=20), Arc(tail=30, weight=12, head=20), Arc(tail=31, weight=2, head=20), Arc(tail=32, weight=18, head=20), Arc(tail=33, weight=-12, head=20), Arc(tail=34, weight=12, head=20), Arc(tail=35, weight=-24, head=20), Arc(tail=36, weight=-12, head=20), Arc(tail=37, weight=-8, head=20), Arc(tail=20, weight=13, head=21), Arc(tail=1, weight=-22, head=22), Arc(tail=2, weight=9, head=22), Arc(tail=3, weight=-25, head=22), Arc(tail=4, weight=25, head=22), Arc(tail=5, weight=10, head=22), Arc(tail=6, weight=7, head=22), Arc(tail=7, weight=10, head=22), Arc(tail=8, weight=-15, head=22), Arc(tail=9, weight=19, head=22), Arc(tail=10, weight=18, head=22), Arc(tail=11, weight=18, head=22), Arc(tail=12, weight=17, head=22), Arc(tail=13, weight=8, head=22), Arc(tail=14, weight=11, head=22), Arc(tail=15, weight=6, head=22), Arc(tail=16, weight=-16, head=22), Arc(tail=17, weight=-18, head=22), Arc(tail=18, weight=-7, head=22), Arc(tail=20, weight=5, head=22), Arc(tail=23, weight=-5, head=22), Arc(tail=24, weight=-24, head=22), Arc(tail=25, weight=-3, head=22), Arc(tail=26, weight=25, head=22), Arc(tail=27, weight=-10, head=22), Arc(tail=28, weight=-20, head=22), Arc(tail=29, weight=16, head=22), Arc(tail=30, weight=14, head=22), Arc(tail=31, weight=17, head=22), Arc(tail=32, weight=10, head=22), Arc(tail=33, weight=-2, head=22), Arc(tail=34, weight=-11, head=22), Arc(tail=35, weight=6, head=22), Arc(tail=36, weight=16, head=22), Arc(tail=37, weight=13, head=22), Arc(tail=1, weight=0, head=23), Arc(tail=2, weight=1, head=23), Arc(tail=3, weight=21, head=23), Arc(tail=4, weight=2, head=23), Arc(tail=5, weight=-23, head=23), Arc(tail=6, weight=-5, head=23), Arc(tail=7, weight=-16, head=23), Arc(tail=8, weight=-13, head=23), Arc(tail=9, weight=-5, head=23), Arc(tail=10, weight=3, head=23), Arc(tail=11, weight=7, head=23), Arc(tail=12, weight=5, head=23), Arc(tail=13, weight=15, head=23), Arc(tail=14, weight=11, head=23), Arc(tail=15, weight=-17, head=23), Arc(tail=16, weight=16, head=23), Arc(tail=17, weight=19, head=23), Arc(tail=18, weight=24, head=23), Arc(tail=20, weight=-3, head=23), Arc(tail=22, weight=-3, head=23), Arc(tail=24, weight=-16, head=23), Arc(tail=25, weight=20, head=23), Arc(tail=26, weight=5, head=23), Arc(tail=27, weight=15, head=23), Arc(tail=28, weight=20, head=23), Arc(tail=29, weight=5, head=23), Arc(tail=30, weight=-15, head=23), Arc(tail=31, weight=-10, head=23), Arc(tail=32, weight=-16, head=23), Arc(tail=33, weight=20, head=23), Arc(tail=34, weight=-11, head=23), Arc(tail=35, weight=5, head=23), Arc(tail=36, weight=-10, head=23), Arc(tail=37, weight=8, head=23), Arc(tail=1, weight=-4, head=24), Arc(tail=2, weight=4, head=24), Arc(tail=3, weight=-11, head=24), Arc(tail=4, weight=-10, head=24), Arc(tail=5, weight=21, head=24), Arc(tail=6, weight=-24, head=24), Arc(tail=7, weight=-19, head=24), Arc(tail=8, weight=0, head=24), Arc(tail=9, weight=2, head=24), Arc(tail=10, weight=14, head=24), Arc(tail=11, weight=10, head=24), Arc(tail=12, weight=5, head=24), Arc(tail=13, weight=21, head=24), Arc(tail=14, weight=3, head=24), Arc(tail=15, weight=-12, head=24), Arc(tail=16, weight=-1, head=24), Arc(tail=17, weight=13, head=24), Arc(tail=18, weight=5, head=24), Arc(tail=20, weight=-5, head=24), Arc(tail=22, weight=4, head=24), Arc(tail=23, weight=-19, head=24), Arc(tail=25, weight=-17, head=24), Arc(tail=26, weight=17, head=24), Arc(tail=27, weight=-12, head=24), Arc(tail=28, weight=13, head=24), Arc(tail=29, weight=3, head=24), Arc(tail=30, weight=12, head=24), Arc(tail=31, weight=8, head=24), Arc(tail=32, weight=24, head=24), Arc(tail=33, weight=-24, head=24), Arc(tail=34, weight=12, head=24), Arc(tail=35, weight=20, head=24), Arc(tail=36, weight=-11, head=24), Arc(tail=37, weight=16, head=24), Arc(tail=1, weight=-23, head=25), Arc(tail=2, weight=-6, head=25), Arc(tail=3, weight=5, head=25), Arc(tail=4, weight=5, head=25), Arc(tail=5, weight=-25, head=25), Arc(tail=6, weight=-16, head=25), Arc(tail=7, weight=2, head=25), Arc(tail=8, weight=14, head=25), Arc(tail=9, weight=-25, head=25), Arc(tail=10, weight=-6, head=25), Arc(tail=11, weight=0, head=25), Arc(tail=12, weight=20, head=25), Arc(tail=13, weight=15, head=25), Arc(tail=14, weight=-25, head=25), Arc(tail=15, weight=15, head=25), Arc(tail=16, weight=21, head=25), Arc(tail=17, weight=0, head=25), Arc(tail=18, weight=-4, head=25), Arc(tail=20, weight=-10, head=25), Arc(tail=22, weight=17, head=25), Arc(tail=23, weight=-24, head=25), Arc(tail=24, weight=-3, head=25), Arc(tail=26, weight=1, head=25), Arc(tail=27, weight=23, head=25), Arc(tail=28, weight=5, head=25), Arc(tail=29, weight=20, head=25), Arc(tail=30, weight=-22, head=25), Arc(tail=31, weight=16, head=25), Arc(tail=32, weight=-6, head=25), Arc(tail=33, weight=-3, head=25), Arc(tail=34, weight=13, head=25), Arc(tail=35, weight=-8, head=25), Arc(tail=36, weight=8, head=25), Arc(tail=37, weight=-6, head=25), Arc(tail=1, weight=-10, head=26), Arc(tail=2, weight=-23, head=26), Arc(tail=3, weight=0, head=26), Arc(tail=4, weight=-9, head=26), Arc(tail=5, weight=19, head=26), Arc(tail=6, weight=-16, head=26), Arc(tail=7, weight=-9, head=26), Arc(tail=8, weight=12, head=26), Arc(tail=9, weight=-17, head=26), Arc(tail=10, weight=0, head=26), Arc(tail=11, weight=20, head=26), Arc(tail=12, weight=0, head=26), Arc(tail=13, weight=13, head=26), Arc(tail=14, weight=-5, head=26), Arc(tail=15, weight=22, head=26), Arc(tail=16, weight=17, head=26), Arc(tail=17, weight=7, head=26), Arc(tail=18, weight=-8, head=26), Arc(tail=20, weight=20, head=26), Arc(tail=22, weight=-1, head=26), Arc(tail=23, weight=24, head=26), Arc(tail=24, weight=-23, head=26), Arc(tail=25, weight=-12, head=26), Arc(tail=27, weight=0, head=26), Arc(tail=28, weight=-9, head=26), Arc(tail=29, weight=-19, head=26), Arc(tail=30, weight=-6, head=26), Arc(tail=31, weight=-13, head=26), Arc(tail=32, weight=25, head=26), Arc(tail=33, weight=1, head=26), Arc(tail=34, weight=-22, head=26), Arc(tail=35, weight=-4, head=26), Arc(tail=36, weight=12, head=26), Arc(tail=37, weight=10, head=26), Arc(tail=1, weight=12, head=27), Arc(tail=2, weight=-19, head=27), Arc(tail=3, weight=18, head=27), Arc(tail=4, weight=-20, head=27), Arc(tail=5, weight=-8, head=27), Arc(tail=6, weight=-12, head=27), Arc(tail=7, weight=10, head=27), Arc(tail=8, weight=19, head=27), Arc(tail=9, weight=-19, head=27), Arc(tail=10, weight=15, head=27), Arc(tail=11, weight=18, head=27), Arc(tail=12, weight=-12, head=27), Arc(tail=13, weight=22, head=27), Arc(tail=14, weight=-10, head=27), Arc(tail=15, weight=-25, head=27), Arc(tail=16, weight=21, head=27), Arc(tail=17, weight=-21, head=27), Arc(tail=18, weight=-16, head=27), Arc(tail=20, weight=-11, head=27), Arc(tail=22, weight=2, head=27), Arc(tail=23, weight=2, head=27), Arc(tail=24, weight=-13, head=27), Arc(tail=25, weight=-1, head=27), Arc(tail=26, weight=8, head=27), Arc(tail=28, weight=-3, head=27), Arc(tail=29, weight=-5, head=27), Arc(tail=30, weight=3, head=27), Arc(tail=31, weight=-17, head=27), Arc(tail=32, weight=21, head=27), Arc(tail=33, weight=-21, head=27), Arc(tail=34, weight=-21, head=27), Arc(tail=35, weight=-24, head=27), Arc(tail=36, weight=24, head=27), Arc(tail=37, weight=-20, head=27), Arc(tail=1, weight=-2, head=28), Arc(tail=2, weight=16, head=28), Arc(tail=3, weight=4, head=28), Arc(tail=4, weight=-5, head=28), Arc(tail=5, weight=10, head=28), Arc(tail=6, weight=19, head=28), Arc(tail=7, weight=-1, head=28), Arc(tail=8, weight=-7, head=28), Arc(tail=9, weight=8, head=28), Arc(tail=10, weight=-15, head=28), Arc(tail=11, weight=-16, head=28), Arc(tail=12, weight=-6, head=28), Arc(tail=13, weight=23, head=28), Arc(tail=14, weight=-11, head=28), Arc(tail=15, weight=13, head=28), Arc(tail=16, weight=17, head=28), Arc(tail=17, weight=-21, head=28), Arc(tail=18, weight=-18, head=28), Arc(tail=20, weight=-22, head=28), Arc(tail=22, weight=10, head=28), Arc(tail=23, weight=6, head=28), Arc(tail=24, weight=-18, head=28), Arc(tail=25, weight=15, head=28), Arc(tail=26, weight=-6, head=28), Arc(tail=27, weight=24, head=28), Arc(tail=29, weight=-21, head=28), Arc(tail=30, weight=-3, head=28), Arc(tail=31, weight=-11, head=28), Arc(tail=32, weight=-22, head=28), Arc(tail=33, weight=-18, head=28), Arc(tail=34, weight=-24, head=28), Arc(tail=35, weight=16, head=28), Arc(tail=36, weight=-10, head=28), Arc(tail=37, weight=-2, head=28), Arc(tail=1, weight=0, head=29), Arc(tail=2, weight=-4, head=29), Arc(tail=3, weight=18, head=29), Arc(tail=4, weight=22, head=29), Arc(tail=5, weight=0, head=29), Arc(tail=6, weight=12, head=29), Arc(tail=7, weight=-23, head=29), Arc(tail=8, weight=-25, head=29), Arc(tail=9, weight=23, head=29), Arc(tail=10, weight=-18, head=29), Arc(tail=11, weight=-25, head=29), Arc(tail=12, weight=-9, head=29), Arc(tail=13, weight=25, head=29), Arc(tail=14, weight=-23, head=29), Arc(tail=15, weight=-7, head=29), Arc(tail=16, weight=-8, head=29), Arc(tail=17, weight=4, head=29), Arc(tail=18, weight=-23, head=29), Arc(tail=20, weight=16, head=29), Arc(tail=22, weight=-7, head=29), Arc(tail=23, weight=-14, head=29), Arc(tail=24, weight=13, head=29), Arc(tail=25, weight=-2, head=29), Arc(tail=26, weight=6, head=29), Arc(tail=27, weight=19, head=29), Arc(tail=28, weight=19, head=29), Arc(tail=30, weight=22, head=29), Arc(tail=31, weight=7, head=29), Arc(tail=32, weight=0, head=29), Arc(tail=33, weight=8, head=29), Arc(tail=34, weight=0, head=29), Arc(tail=35, weight=-15, head=29), Arc(tail=36, weight=-18, head=29), Arc(tail=37, weight=-23, head=29), Arc(tail=1, weight=3, head=30), Arc(tail=2, weight=11, head=30), Arc(tail=3, weight=-17, head=30), Arc(tail=4, weight=21, head=30), Arc(tail=5, weight=1, head=30), Arc(tail=6, weight=22, head=30), Arc(tail=7, weight=12, head=30), Arc(tail=8, weight=6, head=30), Arc(tail=9, weight=3, head=30), Arc(tail=10, weight=14, head=30), Arc(tail=11, weight=-3, head=30), Arc(tail=12, weight=-24, head=30), Arc(tail=13, weight=-12, head=30), Arc(tail=14, weight=7, head=30), Arc(tail=15, weight=16, head=30), Arc(tail=16, weight=14, head=30), Arc(tail=17, weight=-12, head=30), Arc(tail=18, weight=16, head=30), Arc(tail=20, weight=19, head=30), Arc(tail=22, weight=8, head=30), Arc(tail=23, weight=16, head=30), Arc(tail=24, weight=-23, head=30), Arc(tail=25, weight=3, head=30), Arc(tail=26, weight=-9, head=30), Arc(tail=27, weight=-23, head=30), Arc(tail=28, weight=-23, head=30), Arc(tail=29, weight=-22, head=30), Arc(tail=31, weight=1, head=30), Arc(tail=32, weight=-14, head=30), Arc(tail=33, weight=-18, head=30), Arc(tail=34, weight=22, head=30), Arc(tail=35, weight=24, head=30), Arc(tail=36, weight=-16, head=30), Arc(tail=37, weight=-25, head=30), Arc(tail=1, weight=-12, head=31), Arc(tail=2, weight=-24, head=31), Arc(tail=3, weight=3, head=31), Arc(tail=4, weight=2, head=31), Arc(tail=5, weight=20, head=31), Arc(tail=6, weight=21, head=31), Arc(tail=7, weight=-13, head=31), Arc(tail=8, weight=-25, head=31), Arc(tail=9, weight=-4, head=31), Arc(tail=10, weight=25, head=31), Arc(tail=11, weight=10, head=31), Arc(tail=12, weight=-11, head=31), Arc(tail=13, weight=8, head=31), Arc(tail=14, weight=-14, head=31), Arc(tail=15, weight=-7, head=31), Arc(tail=16, weight=-10, head=31), Arc(tail=17, weight=-20, head=31), Arc(tail=18, weight=15, head=31), Arc(tail=20, weight=-10, head=31), Arc(tail=22, weight=3, head=31), Arc(tail=23, weight=3, head=31), Arc(tail=24, weight=-1, head=31), Arc(tail=25, weight=-4, head=31), Arc(tail=26, weight=-2, head=31), Arc(tail=27, weight=-1, head=31), Arc(tail=28, weight=0, head=31), Arc(tail=29, weight=-16, head=31), Arc(tail=30, weight=-4, head=31), Arc(tail=32, weight=-17, head=31), Arc(tail=33, weight=-5, head=31), Arc(tail=34, weight=21, head=31), Arc(tail=35, weight=7, head=31), Arc(tail=36, weight=-15, head=31), Arc(tail=37, weight=16, head=31), Arc(tail=1, weight=-13, head=32), Arc(tail=2, weight=21, head=32), Arc(tail=3, weight=-1, head=32), Arc(tail=4, weight=0, head=32), Arc(tail=5, weight=-9, head=32), Arc(tail=6, weight=21, head=32), Arc(tail=7, weight=0, head=32), Arc(tail=8, weight=-22, head=32), Arc(tail=9, weight=-16, head=32), Arc(tail=10, weight=11, head=32), Arc(tail=11, weight=-12, head=32), Arc(tail=12, weight=1, head=32), Arc(tail=13, weight=-7, head=32), Arc(tail=14, weight=14, head=32), Arc(tail=15, weight=22, head=32), Arc(tail=16, weight=-10, head=32), Arc(tail=17, weight=-11, head=32), Arc(tail=18, weight=-10, head=32), Arc(tail=20, weight=14, head=32), Arc(tail=22, weight=10, head=32), Arc(tail=23, weight=16, head=32), Arc(tail=24, weight=9, head=32), Arc(tail=25, weight=-9, head=32), Arc(tail=26, weight=-18, head=32), Arc(tail=27, weight=25, head=32), Arc(tail=28, weight=-2, head=32), Arc(tail=29, weight=-21, head=32), Arc(tail=30, weight=17, head=32), Arc(tail=31, weight=-19, head=32), Arc(tail=33, weight=-8, head=32), Arc(tail=34, weight=10, head=32), Arc(tail=35, weight=3, head=32), Arc(tail=36, weight=-14, head=32), Arc(tail=37, weight=23, head=32), Arc(tail=1, weight=3, head=33), Arc(tail=2, weight=-1, head=33), Arc(tail=3, weight=5, head=33), Arc(tail=4, weight=3, head=33), Arc(tail=5, weight=-14, head=33), Arc(tail=6, weight=3, head=33), Arc(tail=7, weight=-10, head=33), Arc(tail=8, weight=-3, head=33), Arc(tail=9, weight=4, head=33), Arc(tail=10, weight=-24, head=33), Arc(tail=11, weight=-22, head=33), Arc(tail=12, weight=13, head=33), Arc(tail=13, weight=17, head=33), Arc(tail=14, weight=10, head=33), Arc(tail=15, weight=-17, head=33), Arc(tail=16, weight=-20, head=33), Arc(tail=17, weight=16, head=33), Arc(tail=18, weight=-8, head=33), Arc(tail=20, weight=13, head=33), Arc(tail=22, weight=19, head=33), Arc(tail=23, weight=2, head=33), Arc(tail=24, weight=-24, head=33), Arc(tail=25, weight=-21, head=33), Arc(tail=26, weight=9, head=33), Arc(tail=27, weight=4, head=33), Arc(tail=28, weight=-5, head=33), Arc(tail=29, weight=-3, head=33), Arc(tail=30, weight=-8, head=33), Arc(tail=31, weight=-24, head=33), Arc(tail=32, weight=-25, head=33), Arc(tail=34, weight=-6, head=33), Arc(tail=35, weight=7, head=33), Arc(tail=36, weight=-23, head=33), Arc(tail=37, weight=24, head=33), Arc(tail=1, weight=-4, head=34), Arc(tail=2, weight=5, head=34), Arc(tail=3, weight=19, head=34), Arc(tail=4, weight=14, head=34), Arc(tail=5, weight=-17, head=34), Arc(tail=6, weight=-8, head=34), Arc(tail=7, weight=-25, head=34), Arc(tail=8, weight=-24, head=34), Arc(tail=9, weight=-10, head=34), Arc(tail=10, weight=-23, head=34), Arc(tail=11, weight=17, head=34), Arc(tail=12, weight=10, head=34), Arc(tail=13, weight=-20, head=34), Arc(tail=14, weight=-6, head=34), Arc(tail=15, weight=-16, head=34), Arc(tail=16, weight=-5, head=34), Arc(tail=17, weight=-9, head=34), Arc(tail=18, weight=-4, head=34), Arc(tail=20, weight=0, head=34), Arc(tail=22, weight=-1, head=34), Arc(tail=23, weight=11, head=34), Arc(tail=24, weight=24, head=34), Arc(tail=25, weight=-12, head=34), Arc(tail=26, weight=20, head=34), Arc(tail=27, weight=-9, head=34), Arc(tail=28, weight=-16, head=34), Arc(tail=29, weight=-14, head=34), Arc(tail=30, weight=-18, head=34), Arc(tail=31, weight=-14, head=34), Arc(tail=32, weight=-21, head=34), Arc(tail=33, weight=-10, head=34), Arc(tail=35, weight=24, head=34), Arc(tail=36, weight=0, head=34), Arc(tail=37, weight=-16, head=34), Arc(tail=1, weight=13, head=35), Arc(tail=2, weight=-1, head=35), Arc(tail=3, weight=-19, head=35), Arc(tail=4, weight=-8, head=35), Arc(tail=5, weight=-3, head=35), Arc(tail=6, weight=-8, head=35), Arc(tail=7, weight=-2, head=35), Arc(tail=8, weight=-14, head=35), Arc(tail=9, weight=8, head=35), Arc(tail=10, weight=-19, head=35), Arc(tail=11, weight=-15, head=35), Arc(tail=12, weight=-3, head=35), Arc(tail=13, weight=-3, head=35), Arc(tail=14, weight=-11, head=35), Arc(tail=15, weight=9, head=35), Arc(tail=16, weight=-14, head=35), Arc(tail=17, weight=-11, head=35), Arc(tail=18, weight=12, head=35), Arc(tail=20, weight=13, head=35), Arc(tail=22, weight=7, head=35), Arc(tail=23, weight=12, head=35), Arc(tail=24, weight=-14, head=35), Arc(tail=25, weight=-25, head=35), Arc(tail=26, weight=16, head=35), Arc(tail=27, weight=-19, head=35), Arc(tail=28, weight=24, head=35), Arc(tail=29, weight=18, head=35), Arc(tail=30, weight=22, head=35), Arc(tail=31, weight=-3, head=35), Arc(tail=32, weight=19, head=35), Arc(tail=33, weight=-9, head=35), Arc(tail=34, weight=-10, head=35), Arc(tail=36, weight=15, head=35), Arc(tail=37, weight=-18, head=35), Arc(tail=1, weight=-21, head=36), Arc(tail=2, weight=20, head=36), Arc(tail=3, weight=-6, head=36), Arc(tail=4, weight=-18, head=36), Arc(tail=5, weight=8, head=36), Arc(tail=6, weight=-8, head=36), Arc(tail=7, weight=-8, head=36), Arc(tail=8, weight=1, head=36), Arc(tail=9, weight=10, head=36), Arc(tail=10, weight=-18, head=36), Arc(tail=11, weight=-10, head=36), Arc(tail=12, weight=6, head=36), Arc(tail=13, weight=-16, head=36), Arc(tail=14, weight=3, head=36), Arc(tail=15, weight=-6, head=36), Arc(tail=16, weight=25, head=36), Arc(tail=17, weight=14, head=36), Arc(tail=18, weight=4, head=36), Arc(tail=20, weight=25, head=36), Arc(tail=22, weight=21, head=36), Arc(tail=23, weight=0, head=36), Arc(tail=24, weight=-6, head=36), Arc(tail=25, weight=-17, head=36), Arc(tail=26, weight=-6, head=36), Arc(tail=27, weight=-1, head=36), Arc(tail=28, weight=3, head=36), Arc(tail=29, weight=-21, head=36), Arc(tail=30, weight=-7, head=36), Arc(tail=31, weight=7, head=36), Arc(tail=32, weight=13, head=36), Arc(tail=33, weight=-20, head=36), Arc(tail=34, weight=-1, head=36), Arc(tail=35, weight=20, head=36), Arc(tail=37, weight=25, head=36), Arc(tail=1, weight=-8, head=37), Arc(tail=2, weight=-5, head=37), Arc(tail=3, weight=20, head=37), Arc(tail=4, weight=-16, head=37), Arc(tail=5, weight=4, head=37), Arc(tail=6, weight=18, head=37), Arc(tail=7, weight=-24, head=37), Arc(tail=8, weight=-20, head=37), Arc(tail=9, weight=6, head=37), Arc(tail=10, weight=-23, head=37), Arc(tail=11, weight=-5, head=37), Arc(tail=12, weight=6, head=37), Arc(tail=13, weight=0, head=37), Arc(tail=14, weight=-3, head=37), Arc(tail=15, weight=11, head=37), Arc(tail=16, weight=-6, head=37), Arc(tail=17, weight=4, head=37), Arc(tail=18, weight=-9, head=37), Arc(tail=20, weight=20, head=37), Arc(tail=22, weight=23, head=37), Arc(tail=23, weight=25, head=37), Arc(tail=24, weight=6, head=37), Arc(tail=25, weight=4, head=37), Arc(tail=26, weight=12, head=37), Arc(tail=27, weight=13, head=37), Arc(tail=28, weight=1, head=37), Arc(tail=29, weight=16, head=37), Arc(tail=30, weight=-21, head=37), Arc(tail=31, weight=-13, head=37), Arc(tail=32, weight=-4, head=37), Arc(tail=33, weight=-6, head=37), Arc(tail=34, weight=-15, head=37), Arc(tail=35, weight=15, head=37), Arc(tail=36, weight=-3, head=37)],17)                                                                                         #Graph 1 :Graph with more than one cycles 
#l=m.max_spanning_arborescence([Arc(1,5,0),Arc(2,1,0),Arc(3,1,0),Arc(2,11,1),Arc(3,4,1),Arc(3,5,2),Arc(1,100,2),Arc(1,9,3),Arc(2,8,3)],0)
#l=m.max_spanning_arborescence([Arc(tail=2, weight=-8, head=1), Arc(tail=3, weight=-14, head=1), Arc(tail=4, weight=7, head=1), Arc(tail=5, weight=7, head=1), Arc(tail=1, weight=21, head=2), Arc(tail=3, weight=3, head=2), Arc(tail=4, weight=8, head=2), Arc(tail=5, weight=-16, head=2), Arc(tail=1, weight=-11, head=3), Arc(tail=2, weight=13, head=3), Arc(tail=4, weight=4, head=3), Arc(tail=5, weight=-10, head=3), Arc(tail=1, weight=-24, head=4), Arc(tail=2, weight=17, head=4), Arc(tail=3, weight=-20, head=4), Arc(tail=5, weight=3, head=4), Arc(tail=1, weight=1, head=5), Arc(tail=2, weight=10, head=5), Arc(tail=3, weight=-2, head=5), Arc(tail=4, weight=-23, head=5)],3)
#print ('\n\n',l)
 

#l=m.max_spanning_arborescence([Arc(1,1,0),Arc(2,2,0),Arc(3,3,0),Arc(2,4,1),Arc(3,1,2),Arc(4,7,3),Arc(3,6,4),Arc(1,5,2)],0)              #Graph 1 :Graph with more than one cycles 
#l=m.max_spanning_arborescence([Arc(1,5,0),Arc(2,1,0),Arc(3,1,0),Arc(2,11,1),Arc(3,4,1),Arc(3,5,2),Arc(1,10,2),Arc(1,9,3),Arc(2,8,3)],0) #Graph 2:Graph with more than one cycles        
#l=m.max_spanning_arborescence([Arc(2 ,1,1),Arc(3,3,2),Arc(5,4,3),Arc(6,3,5),Arc(5,2,4),Arc(5,1,2),Arc(4,1,7),Arc(1,2,4),Arc(4,1,3)],7)  #Graph 3:Changing the root node of Graph 1 gives us a different spanning arborescence          
#l=m.max_spanning_arborescence([Arc(2,5,1),Arc(1,-2,2),Arc(2,-3,3),Arc(4,-4,1),Arc(2,7 ,4),Arc(4,9,3),Arc(3,8,1),Arc(1,6,0),Arc(3,7,0)],0)#Graph 4:Graph with negative edges
#l=m.max_spanning_arborescence([Arc(1, 9, 0), Arc(2, 10, 0), Arc(3, 9, 0), Arc(2, 20, 1), Arc(3, 3, 1), Arc(1, 30, 2), Arc(3, 11, 2), Arc(2, 0, 3), Arc(1,30, 3)], 0)#Graph 5:On reversing all the edges of the graph we do not get a spanning arborescence
#l=m.max_spanning_arborescence([Arc(1,5,0),Arc(2,5,0),Arc(3,5,0),Arc(4,5,0),Arc(0,6,1),Arc(2,6,1),Arc(3,6,1),Arc(4,6,1),Arc(0,7,2),Arc(1,7,2),Arc(3,7,2),Arc(4,7,2),Arc(0,8,3),Arc(1,8,3),Arc(2,8,3),Arc(4,8,3),Arc(0,9,4),Arc(1,9,4),Arc(2,9,4),Arc(3,9,4)],0) #Graph 5 : Complete graph of 5 nodes              
#l=m.max_spanning_arborescence([Arc(0,10,0),Arc(1,9,1),Arc(2,10,2)],0)  #Graph 6 : Fails to give an arborescence for a null or disconnected graph
#l=m.max_spanning_arborescence([Arc(1,9,0),Arc(2,8,0),Arc(2,10,1),Arc(1,1,2),Arc(2,6,3),Arc(3,7,2),Arc(1,12,3)],0) #Graphs with varying edge weights 
#l=m.max_spanning_arborescence([Arc(1,18,0),Arc(2,9,0),Arc(2,10,1),Arc(1,50,2)],0)  
#l=m.max_spanning_arborescence([Arc(1,5,0),Arc(2,1,0),Arc(3,1,0),Arc(2,11,1),Arc(3,4,1),Arc(3,50,2),Arc(1,100,2),Arc(1,9,3),Arc(2,8,3)],0)
#l=m.max_spanning_arborescence([Arc(1,5,0),Arc(2,1,0),Arc(3,1,0),Arc(2,110,1),Arc(3,4,1),Arc(3,5,2),Arc(1,10,2),Arc(1,9,3),Arc(2,8,3)],0)
#l=m.max_spanning_arborescence([Arc(1,1,0),Arc(2,2,0),Arc(3,3,0),Arc(5,4,0),Arc(2,100,1),Arc(5,7,4),Arc(4,10,3),Arc(5,5,2),Arc(2,6,5),Arc(3,11,2)],0)  
#l=m.max_spanning_arborescence([Arc(1,4,0),Arc(2,5,0),Arc(3,6,0),Arc(4,7,0),Arc(1,10,2),Arc(2,20,1),Arc(3,1,2),Arc(4,30,3),Arc(3,20,4)],0)