graph = {
    'A': set("HB"),
    'B': set("AD"),
    'C': set("D"),
    'D': set("BCIK"),
    'E': set("FK"),
    'F': set("EG"),
    'G': set("FHK"),
    'H': set("AIJKG"),
    'I': set("HJD"),
    'J': set("KIH"),
    'K': set("HJGED")    
}

def welsh_powell(graph):
    ordered = sorted([(k, len(v)) for k, v in graph.items()], key=lambda x: -x[1])
    
    coloring = {}
    
    cnt = 0
    while len(ordered) > 0:
        fst = ordered.pop(0)
        idxs = set()
        coloring[fst[0]] = cnt
        forbidden = set(graph[fst[0]])
        for i, ele in enumerate(ordered):
            if not ele[0] in forbidden:
                coloring[ele[0]] = cnt
                forbidden |= graph[ele[0]]
                idxs.add(i)
        ordered = [ordered[i] for i in range(len(ordered)) if not i in idxs]
        cnt += 1

    print(coloring)
    return cnt

print(welsh_powell(graph))

tests = [
    ("""
abcdefg
abcdefg:
abcdefg
abcdefg
""", 2)
    ]
#101201
from collections import deque

def build_graph(st):
    graph = {}
    lines = st.strip().split('\n')
    n, m = len(lines), len(lines[0])
    visited = set()
    seen = set([(x, y) for x in range(n) for y in range(m)])
    while len(seen) > 0:
        x, y = seen.pop()
        symb = lines[x][y]

        queue = deque([(x, y)])
        graph[symb] = set()
        while queue:
            u, v = queue.pop()
            for du, dv in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                a, b = u + du, v + dv
                if 0 <= a < n and 0 <= b < m:
                    other = lines[a][b]
                    if other == symb and not (a, b) in visited:
                        visited.add((a, b))
                        queue.append((a, b))
                        seen.discard((a, b))
                    elif other != symb:
                        graph[symb].add(other)
        # print(symb, visited)
    return graph
for st, r in tests:
    g = build_graph(st)
    s = welsh_powell(g)
    print(g)
    print(s, r)