注：厳密な解説ではありません

大筋は公式解説を参照ください。

\(2\leq K\) の場合について、綺麗な構成方法が思いつかなくても乱択を用いることによって構成できます。

サイクルを決めた時、条件を満たしているかは例えば \(O(N^K)\) の計算量でわかります（すべての移動量を全探索する）。もっと高速にもなりますが、\(K\leq 3\) なのでこれで十分高速です。

まずすべての配り方を達成できるようにする場合（\(N\) 偶数の \(K=2\) と、\(5\leq N\) の \(K=3\)）についてですが、これは素直に全てのサイクルをランダムに取れば良いです。直感的にも、十分速く答えが見つかりそうだとわかります。

そうでない場合、\(1,2\) の場所が固定されていてBanされる距離が \(N\) の約数のどれか、と言う問題を解きたくなります（多分これが一番楽な実装だと思います）。これも \(1,2\) の場所を固定して乱択すれば実測上十分高速なことがわかります。

なんとなくサイクルが見つかる確率を見積もると \(N!/N^N\) 程度で、実際はもっと確率が高そうなのと、試行回数を大量に取れることも考えると十分です。不安であれば、手元で回した結果をすべて埋め込めば良いです。

余談：サイクル分解については、「グラフが与えられた時、通る辺の数が一番多いサイクル分解」を求めるDPを実装しておくと、\(K=1\) の判定の際はすべての辺を通っているか判定すれば良く、\(K=2\) の判定の際は補グラフにしたときに通った辺が全部グラフの辺か判定すれば良く、使い回せて楽です。

公式解説では端折られているので軽く触れておくと、\(DP[S][i]\) を「\(S\) に含まれる頂点からなり、頂点 \(\min(S)\) から始まり、頂点 \(i\) で終わるパスが通る辺の最大本数」と定義しておくと頂点集合を固定したときの値が \(O(2^NN^2)\) とかで求まり、これを \(O(3^N)\) の部分集合DPでまとめればよいです。（サイクルのサイズを持っておきたいので適当にやるとテーブルのサイズは \(O(2^NN)\) とかになりますが、各部分集合についてその集合で更新したい場所は \(1\) 箇所しかないので、計算量に \(N\) は掛かりません。）