结论：合法的必要条件为图为二分图
证明：
一条边的两端\(a_i\)奇偶性不同
我们的操作可以描述成：
\(a_u-a_v=1\)或\(|a_u-a_v|=1\)
考虑差分约束
\(a_u-a_v=1\)显然
\(|a_u-a_v|=1\)考虑化成\(a_u-a_v\le 1,a_v-a_u\le 1\)
正确性：
即证明\(|a_u-a_v|=1\)不会存在\(a_u=a_v\)
我们发现上述连边均满足\(a_i\)奇偶不同，故不会存在\(a_u=a_v\)的情况
剩下的比较简单就不讲了
原文：https://www.cnblogs.com/Grice/p/14122931.html