First, it is sufficient to consider that you may use “at most \(K\) colors” instead of “exactly \(K\) colors”; then you can apply the inclusion-exclusion principle to find the answer to the original problem.
So we consider the following:

Subproblem

How many graphs can be obtained by choosing an unlabeled graph (where vertices are not labeled) with \(N\) vertices and writing an integer between \(1\) and \(K\) on each vertex?

Since an unlabeled graph is hard to handle, we bring up a labeled graph (where vertices are labeled) to rephrase it as follows (where \(S_N\) is a set of permutations of size \(N\)):

Subproblem (labeled ver.)

How many graphs can be obtained by choosing a labeled graph with \(N\) vertices and writing an integer between \(1\) and \(K\) on each vertex?
Here, two graphs are considered the same if and only if:

• there exists a permutation \(p \in S_N\) such that, re-labelling the vertices of one graph by \(v_i \to v_{p_i}\) simultaneously equalizes the colors of vertices and existence of edges between vertices in the two graphs. \((\ast)\)

(We simply refer to the condition \((\ast)\) by “isomorphic up to labels.”) Let \(G\) be the set of all labeled graphs. For a labeled graph \(g\), we denote by \(p(g)\) the graph obtained by re-labelling the vertices of \(g\) by \(v_i \to v_{p_i}\).

First, we have the following fact.

Let \(g\) be a graph in \(G\). Define \(A(g)\) and \(B(g)\) as follows:

• \(A(g)\): the number of labeled graph in \(G\) that is isomorphic up to labels
• \(B(g)\): the number of permutations \(p\) such that \(p(g)\) is isomorphic (as a labeled graph) to \(g\)

Then, \(A(g) B(g) = N!\).

This is justified by the one-to-one correspondence between any graph \(h\) isomorphic to \(g\) up to labels and \(B(g)\) permutations \(p_1, p_2, \dots, p_{B(g)}\) such that \(p_i(g)\) is isomorphic to \(h\).

With this fact, we have the following equation:

Pólya enumeration theorem (applied to this problem)

Let \(G'\) be the set of undirected graphs that are obtained by unlabeling a graph in \(G\). For a permutation \(p\), a graph \(g\) such that \(\lbrace g \vert g \in G, p(g) = g \rbrace\) is called a fixed point.
Then, the size of \(G'\) is the average of the number of fixed points over all permutations \(p\). Formally, we have the following equation:

\[N! \cdot |G'| = \sum_{p \in S_n} \vert \lbrace g \vert g \in G, p(g) = g \rbrace \vert\]

We first deform the left hand side. Every unlabeled graph generated from an element of \(G\) occurs once as an element of \(G'\). For an unlabeled graph \(g'\), there are \(A(g)\) graphs in \(G\) that turns into \(g'\) by removing the labels. Thus we have

\[N! \cdot |G'| = N! \cdot \sum_{g \in G} \frac{1}{A(g)} = \sum_{g \in G} B(g).\]

The right hand side can be represented by a double sum where we can swap the order of \(\sum\):

\[ \begin{aligned} &\sum_{p \in S_n} \vert \lbrace g \vert p(g) = g \rbrace \vert \\ &= \sum_{p \in S_n} \sum_{g \in G} \lbrack p(g) = g \rbrack \\ &= \sum_{g \in G} \sum_{p \in S_n} \lbrack p(g) = g \rbrack \\ &= \sum_{g \in G} \vert \lbrace p \vert p \in S_n, p(g) = g \rbrace \vert. \end{aligned} \]

(\(\lbrack \mathrm{cond} \rbrack\) is a function that returns \(1\) if \(\mathrm{cond}\) is true and \(0\) otherwise)
This \( \lbrace p \vert p \in S_n, p(g) = g \rbrace\) is nothing but \(B(g)\), so the both hand sides turn out to be equal.

According to the equation, we find that the answer to the subproblem, \(|G'|\), can be computed by:

\[\frac{1}{N!}\sum_{p \in S_n} \vert \lbrace g \vert g \in G, p(g) = g \rbrace \vert.\]

This way, we can eliminate the condition that “isomorphic up to labels,” simplifying the objects to count.
Like this problem, a combinatoric problem that requires to identify graphs up to permutations can be solved by finding the average of the fixed points. Such a technique also appears in a combinatoric problem on a cycle or a cube, as in ABC198F. (Pólya’s theorem also holds when the set of permutations to apply is well-behaving.)

Anyway, we can evaluate the expression by counting the number of labeled graphs such that \(p(g) = g\) for each fixed permutation \(p\) and averaging the value over all permutations. When the sizes of cycles in the cycle decomposition of a permutation is \((c_1, c_2, \dots, c_m)\), the number of such graphs equals

\[K^m \times \mathrm{pow}\left(2, \sum_{i=1}^m \left(\lfloor c_i/2\rfloor + \sum_{j=1}^{i-1} \gcd(c_i, c_j)\right) \right)\]

Therefore, just as ABC226F, we enumerate all partitions of a natural number \(N\) and sum up (the number of permutations that is decomposed to such cycles) \(\times\) (the number of graphs). We can compute it in a total of \(\mathrm{O}(p(N) \mathrm{poly}(N))\) time, where \(p(n)\) is the \(n\)-th partition number; this is fast enough for the execution time limit.

• With an appropriate implementation, it can be computed in a total of \(\mathrm{O}(p(N) N)\), but \(\mathrm{O}(p(N) N^3)\) would suffice to get AC (accepted) within the TL (time limit). Sample code (\(\mathrm{O}(p(N) N^3 \log N)\), 146 ms)

Note that the \(K=1\) version of this problem counts the number of unlabeled graph. Thus, the solution to this problem also enables to count unlabeled graphs in an \(\mathrm{O}(p(N) N)\) time as well.