import re
from collections import defaultdict
from itertools import count


connection_re = r

class Graph:

    def __init__(self, name, connections):
        self.name = name
        self.connections = connections
        g = self.graph = defaultdict(list)  

        matches = re.finditer(connection_re, connections,
                              re.MULTILINE | re.VERBOSE)
        for match in matches:
            n1, n2, n = match.groups()
            if n:
                g[n] += []
            else:
                g[n1].append(n2)    
                g[n2].append(n1)

    def greedy_colour(self, order=None):
        
        if order is None:
            order = self.graph      
        colour = self.colour = {}
        neighbours = self.graph
        for node in order:
            used_neighbour_colours = (colour[nbr] for nbr in neighbours[node]
                                      if nbr in colour)
            colour[node] = first_avail_int(used_neighbour_colours)
        self.pp_colours()
        return colour

    def pp_colours(self):
        print(f)
        c = self.colour
        e = canonical_edges = set()
        for n1, neighbours in sorted(self.graph.items()):
            if neighbours:
                for n2 in neighbours:
                    edge = tuple(sorted([n1, n2]))
                    if edge not in canonical_edges:
                        print(f)
                        canonical_edges.add(edge)
            else:
                print(f)
        lc = len(set(c.values()))
        print(f)


def first_avail_int(data):
    
    d = set(data)
    for i in count():
        if i not in d:
            return i


if __name__ == '__main__':
    for name, connections in [
            ('Ex1', ),
            ('Ex2', ),
            ('Ex3', ),
            ('Ex4', ),
            ]:
        g = Graph(name, connections)
        g.greedy_colour()