题意

cf

做法

结论：合法的必要条件为图为二分图

证明：
一条边的两端\(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\)的情况

剩下的比较简单就不讲了