当 $M\ge N$ 时，原问题无解。因为此时至少需要让大小为 $1,2,\cdots, M$ 的连通块都出现一次，占用 $2\times \frac{M(M+1)}{2}$ 个格子。这个值不能超过 $N^2$，解得 $M< N$。

显然 $M=N-1$ 的问题最为困难，先尝试解决它。接下来以 $N=8$ 为例。

一个思路是尝试先构造出大小为 $N-1$ 的黑白两种颜色的连通块，然后再构造出 $N-2$ 的，然后是 $N-3$ 的，以此类推。可以找到如下模式：

描述：

• 第 $2i-1$ 行除了第 $n-i+1$ 个是白色，其他都是黑色；
• 第 $2i$ 行除了第 $n-i+1$ 个是黑色，其他都是白色（与第 $2i-1$ 行相反）。

可以发现其满足条件，经过验证后这个构造能解决 $N$ 为偶数的情况。

然而 $N$ 为奇数的情况仍旧需要调整。以下是 $N=9$ 时的错误构造结果：

观察我们的错误构造，一个问题是，白色的点中有两个大小为 $1$ 的连通块。我们尝试将第一行直接删除，以移除那个浪费的大小为 $1$ 的白色连通块，然后在最后一行做一些动作。先将最后一行全部填充黑色：

此时，我们的白色连通块的大小缺少了 $4$ 和 $5$。如果将第一行的那里分割开来：

我们会少一个大小为 $9$ 的连通块，然后多两个大小为 $4$ 的连通块。一多一少相互抵消了！这不好。一个改法是修改第一行分割的位置，把第一行那个大小为 $9$ 的连通块分割为大小为 $3$ 和大小为 $5$ 的连通块，然后修改倒数第二行的点，让那个大小为 $3$ 的连通块变成大小为 $4$ 的连通块：

白色的连通块此时已经满足条件。接下来看黑色的，我们发现黑色还差一个大小为 $1$ 的黑色连通块，把右下角隔开就好：

总结：

• 在 $N$ 为偶数的基础上，删除第一行，在最后补上一个全黑行；
• 将第一行第 $(N+3)/2$ 个位置改成黑色；
• 将倒数第二行最后一个改成白色；
• 将最后一行倒数第二个改成白色。

接下来考虑 $M$ 不一定为 $N-1$ 的情况。首先，当 $M\le \lfloor N/2\rfloor $ 时，有以下构造：

一圈一圈往外拓展直到连通块数量足够即可。

此时 $M>\lfloor N/2\rfloor$，我们先考虑偶数的情况。当 $N=10,M=8$ 时，在 $M=9$ 的基础上断开第三行第一个：

当 $M=7$ 时，同时断开第三行前两个与第五行前两个：

总结：将第 $2i+1$ 行将前 $N-M-i$ 个设为白色。

当 $N$ 为奇数时同理。当 $N=9,M=7$ 时，注意，因为第二行的连续段大小为 $8$，而第四行的为 $6$，为了让黑色也减少一种，于是需要将第二行前两个都删除：

当 $M=6$ 时，就是第二行第四行都各再删一个：

当 $M=5$ 时，就是第二第四第六行都各再删一个：

总结：将第 $2i$ 行将前 $N-M-i+[i=1]$ 个设为白色。

$N\le 5$ 可能需要跑暴力。