考虑先做出 $n = 12K$ 的部分分。

注意到每个点的度数不能超过 $K$，而一共有 $2K$ 个节点，自然想到将这 $2K$ 个点分成编号为 $0 \sim K - 1$ 的小点和编号为 $K \sim 2K - 1$ 的大点。

我们记小点为 $\text{A}$，大点为 $\text{B}$，则一条路径本质上会有 $\text{AAA}$，$\text{AAB}$，$\text{ABA}$，$\text{ABB}$ 这四种情况，我们分别进行分类讨论（$\text{B}$ 开头的方案本质同构，不做展开）。

$\text{AAA},\text{ABA}$ 是简单的，分别构造完全图，二分图即可。需要花费共 $4K$ 条边。

考虑 $\text{AAB}$ 怎么做，我们考虑继续进行分类讨论，将 $\text{A}$ 继续平均拆分为 $a_0,a_1$，$\text{B}$ 继续拆分为 $b_0,b_1$，进行以下构造：

就得到了一个 $K$ 为偶数的 $12K$ 个点的构造方案。

继续考虑 $K$ 为奇数的情况怎么做，此时有 $|a_0| = |a_1| - 1$，$|b_0| = |b_1| - 1$。

注意到如果我们将 $K$ 为偶数的构造方案沿用到 $K$ 为奇数上时，$a_1a_0b_1,a_0a_1b_0$ 这幅图的最大度数为 $K + 1$，会爆炸，考虑进行调整，我们只需要将 $a_1a_0b_1,a_0a_1b_0$ 中的小点的 $(i,\frac{K}{2} + i)$ 和大点的 $(K+i,K+\frac{K}{2} + i)$ 这些连边删除，然后在 $a_0a_0b_1,a_1a_1b_0$ 这幅图中加上这些边即可完成构造（即小点的 $(i,\frac{K}{2} + i)$ 和大点的 $(K+i,K+\frac{K}{2} + i)$），共 $12K$ 个点。

考虑 $K \le 5$ 的包。

猜测每个点度数为 $K$，且每种颜色出现的次数平均时是有解的，考虑初始构造这么一个图，对着这个图跑退火，每次操作可以交换两个点的颜色或者将两条边 $(x,y),(u,v)$ 修改为 $(x,u),(y,v)$，实现的好的话 10s 内就能跑出一个解。