まず、「ちょうど \(K\) 色使う」という制約を「\(K\) 色の中からいくつかの色を使う」という制約に替えた問題が解ければ、元の問題の答えは包除原理を利用して計算できます。
よって、次の問題が解ければよいです。

部分問題

\(N\) 頂点の unlabeled graph(頂点ラベルなしグラフ) を 1 つ選び、各頂点に \(1\) から \(K\) までの整数のいずれかを書きこむ。得られるグラフの通り数は？

この部分問題は unlabeled graph の部分が扱いづらいので、 labeled graph(頂点ラベルつきグラフ) を登場させると次のように読み替えられます。(ここで \(S_N\) は 長さ \(N\) の置換の集合)

部分問題(labeled ver.)

\(N\) 頂点の labeled graph を 1 つ選び、各頂点に \(1\) から \(K\) までの整数のいずれかを書きこむ。得られるグラフの通り数は？
ただし、2 つのグラフは次の条件を満たすときに同じグラフであるとみなす。

• ある置換 \(p \in S_N\) が存在して、一方のグラフの頂点のラベルを \(v_i \to v_{p_i}\) にすべて同時に張り替えると、2 つのグラフの頂点の色・頂点間の辺の有無がすべて一致する。\((\ast)\)

(以下では \((\ast)\) の条件を 「ラベルを取り除くと同型である」と呼びます)
\(G\) を labeled graph の全体集合とします。また、labeled graph である \(g\) に対してグラフ \(p(g)\) を \(g\) の頂点ラベルを \(v_i \to v_{p_i}\) に張り替えたものとします。

まず、次の事実が成り立ちます。

\(G\) からグラフを 1 つ選び \(g\) とする。\(A(g), B(g)\) を次のように定める。

• \(A(g)\) : \(G\) の要素のうち、ラベルを取り除くと同型であるような labeled graph の個数
• \(B(g)\) : \(p(g)\) が \(g\) と (labeled graph として) 同型であるような置換 \(p\) の個数

このとき \(A(g) B(g) = N!\) が成り立つ。

これは、すべての \(g\) とラベルを取り除くと同型なグラフ \(h\) に対して、\(B(g)\) 個の順列 \(p_1, p_2, \dots, p_{B(g)}\) であって \(p_i(g)\) が \(h\) と同型であるものが一対一対応することから証明できます。

この事実を利用すると、次の式が成り立ちます。

Polya の数え上げ定理(Burnside の補題, Cauchy–Frobenius の補題とも) をこの問題に適用した式

\(G\) に含まれるグラフのラベルを取り除いた unlabeled graph の集合を \(G'\) とする。また、置換 \(p\) に対して \(\lbrace g \vert g \in G, p(g) = g \rbrace\) を満たす \(g\) を不動点と呼ぶ。
このとき \(G'\) の大きさは すべての置換 \(p\) に対する不動点の個数の平均となる。すなわち次の式が成り立つ。

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

まず、左辺を変形します。\(G'\) の要素には \(G\) の元から生成できるすべての unlabeled graph が 1 回ずつ登場します。unlabeled graph を 1 つ取ってきて \(g'\) とするとラベルを取り除くと \(g'\) になるようなグラフ \(g\) は \(G\) に \(A(g)\) 個含まれています。よって

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

と変形できます。
次に右辺を二重和の形で表して \(\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\) は \(\mathrm{cond}\) が真ならば \(1\), 偽ならば \(0\) を取る関数)
この \( \lbrace p \vert p \in S_n, p(g) = g \rbrace\) はまさに \(B(g)\) です。よって両辺が一致することが確認できました。

この式を利用すると、部分問題の答えは \(|G'|\) なので、

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

を計算する問題に言い換えることができました。

この言い換えによって「ラベルを取り除くと同型」という条件を取り除いた状態でグラフを数えることができるようになり、 数え上げる対象を簡単にすることができます。
この問題のように、置換を作用させて一致すると同型になるものを 1 個として数える問題は、Polya の数え上げ定理を利用して不動点の平均に言い換えることができます。このテクニックは円環の数え上げや ABC198F のような立方体の数え上げで登場します。(Polya の数え上げ定理は作用させる置換の集合がよい性質を持つ時にも成り立ちます。)

さて、置換 \(p\) を固定したときに \(p(g) = g\) となる labeled graph の個数を数えて、それらをすべての置換に対して足し合わせて平均を取ればこの式を計算できます。置換をサイクル分解したときのサイクルの大きさの列が \((c_1, c_2, \dots, c_m)\) であるとき、グラフの個数は

\[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)\]

になることが確認できます。よって ABC226F のように 自然数 \(N\) の分割をすべて列挙して、各分割に対して (分割がそのようになる置換の通り数) \(\times\) (グラフの通り数) を足し合わせればよく、これは \(n\) 番目の分割数を \(p(n)\) として \(\mathrm{O}(p(N) \mathrm{poly}(N))\) で計算できて、これは十分実行時間に間に合います。

• 適切に実装すると問題全体で \(\mathrm{O}(p(N) N)\) で計算できますが、制約が小さいので \(\mathrm{O}(p(N) N^3)\) 程度の計算量でも TL に余裕を持って AC できると思います。実装例 (\(\mathrm{O}(p(N) N^3 \log N)\), 146 ms)

なお、この問題の \(K=1\) の場合は unlabeled graph の数え上げに相当します。この問題の解法を利用すれば、 unlabeled graph の数え上げも \(\mathrm{O}(p(N) N)\) で計算できます。