题目大意
给定一张 $N$ 个点 $M$ 条边的无向图，以及一个参数 $K$，保证 $M\geq 2KN$。请找出一种给无向图的每个顶点染上红、蓝、白三种颜色的方案，使得：
- 至少有一个红色或蓝色的顶点；
- 每个红色顶点至少有 $K+1$ 个蓝色邻居；
- 每个蓝色顶点至少有 $K+1$ 个红色邻居。
可以证明一定有解。
数据范围
多组测试，保证 $1\leq N,M,K\leq 5\times 10^4$，$M\geq 2KN$ 且所有测试数据的 $M$ 总和不超过 $5\times 10^4$。
解题过程
我们首先考虑给所有顶点染上红色或蓝色的一种，使得至少有 $\frac{1}{2}M$ 条边的两端点异色。如果异色的边数不到总边数的一半，则容易知道至少存在一个顶点，其异色邻居个数小于同色邻居的个数。此时我们可以翻转该顶点的颜色，这样异色的边数一定会至少增加 $1$，因而该调整法至多执行 $\frac{1}{2}M$ 轮便会终止。
假设现在至少有 $\frac{1}{2}M$ 条边为异色边，由 $M\geq 2KN$ 可知此时至少有 $KN$ 条异色边。若有一个顶点的异色邻居个数不超过 $K$，则我们将该顶点修改为白色，此时有色顶点个数减少 $1$，而连接一个红色顶点一个蓝色顶点的异色边个数至多减少 $K$。可以得出，在调整的过程中，异色边的个数一定超过有色顶点个数的 $K$ 倍。
若调整法过程中，仅剩一个有色顶点，则此时异色边数量必然为 $0$，与上述性质矛盾，故而调整法得到的解一定有 $>1$ 个有色顶点，即得到的解一定是一个满足题意的构造。
由于每轮翻转颜色操作会影响 $O(N)$ 个邻居，而该操作会进行至多 $O(M)$ 次，可以说明上述做法的时间复杂度为 $O(NM)$。在 $M\leq 5\times 10^4$ 的数据范围下，该时间复杂度不一定可以接受。
我们考虑在所有染色方案中，随机任意一种染色方案。可以算出，此时异色边数量的均值为 $\mu=\frac{1}{2}M$，而方差为 $\sigma^2=\frac{1}{4}M$。若调整法执行了 $k$ 轮，则初始边的数量一定不超过 $\frac{1}{2}M-k$ 条。根据切比雪夫不等式可知，该事件发生的概率满足：
$$ P(x\leq \mu-k)\leq \frac{\sigma^2}{k^2} $$
故可以说明，对于 $k=c\sqrt M$，该事件仅有不超过 $\frac{1}{4c^2}$ 的概率发生，可以认为，有足够高的概率 $k$ 为 $O(\sqrt M)$ 级别，即时间复杂度为 $O(N \sqrt M)$。