Arpa’s overnight party and Mehrdad’s silent entering

题目大意

给 nn 对情侣染色，要求情侣不能然相同颜色而且相邻 33 人的颜色不同，求合法方案。

数据范围满足 1≤n≤1051\le n\le 10^5。

思路

钦定 2i−12i-1 与 2i2i 的人吃的食物不一样，那么这样建图跑出来的一定是二分图。

因为所有图中的换都是由 xx 条 2i−12i-1 与 2i2i 的边与 xx 条情侣之间的边组成的长度为 2x2x 的偶环，一定不存在奇环。

Submission #269643071 - Codeforces