yb 的题解。

给定坐标轴上的 $n$ 个点，给每个点一种颜色（红/蓝），使得每行每列两种颜色的点的个数之差不超过 $1$

$1 \le n \le 2 \times 10^5$，$1 \le x_i, y_i \le 2n$

参考这篇题解的做法，大致是将所有横、纵坐标相同的点两两配对连边跑二分图染色。正确性显然，每行每列至多剩余一个红或蓝点。非常妙啊，这里证明一下为什么是对的，即为什么这样的图是二分图（不存在奇环）。

因为每个点至多连出一条横边，一条竖边，所以在一条路径上横边竖边一定是交替出现的。所以存在环时环上横边竖边数量一定相等（有点像小学那种环上种树树和间隔的问题），那就一定是偶环了。

CF741C 和这道题很像。