每个颜色必须连通，所以每种颜色的边数至少是 $N-1$，总边数 $N(N-1)/2$，所以 $K\le N/2$。

注意到 $K$ 变小的时候可以直接合并两种颜色，所以我们只需要考虑 $K=N/2$ 的情况。

如果 $N$ 是偶数可以这样构造：对每个 $i=1,\ldots,N/2$，连接 $(i,i+N/2)$，并对每个 $j=1,\ldots,N/2-1$，连接 $(i,i+j)$ 和 $(i+N/2,i+N/2+j)$。这样每个颜色的直径不超过 $3$。

如果 $N$ 是奇数，先构造 $N-1$ 的答案，然后 $N$ 向之前的点连每种不同颜色的边即可，这样直径不超过 $4$。