非常神的题目啊。

考虑不加边的时候这个问题怎么解决。显然照搬 CF547D ，建立虚点，将虚点与原图所有度数为奇数的点连边，跑个欧拉回路，对回路上的边黑白染色，即可达到答案下界： 。

接下来考虑图上加边怎么处理。现在无法再沿用虚点，因为原图上加边会引起虚点上的加边删边，很难维护。但如果把虚点拆掉，注意到欧拉回路会分成许多环和路径，考虑直接维护这些环和路径。

在一般图中是做不到的，但这题是二分图。况且，每个点只可能是一条路径的端点，如果有多于一条路径以同一个点为端点，这些路径自然可以接起来。

对每条边赋权值 ，表示其从左部指向有部还是从右部指向左部。

考虑加一条边 的情况：

1. 如果 和 都不是某条路径的端点，那直接将 作为一条新路径即可。
2. 如果 是某条路径的端点而 不是，那将 接到 所在路径上即可。
3. 如果 和 都是某条路径的端点，那就要分类讨论。如果这两条路径同向，那么将这条边改到对应的方向即可。否则，我们需要整体翻转一条路径，并将这两条路径于这条边合并。

我们需要一个支持整体翻转和合并的数据结构，标算写的是启发式合并堆。但实际上有非常简单的带权并查集维护法，毕竟我们并不考虑路径中点的具体顺序，只考虑路径的点集和每条边的权值（方向）。

简略介绍带权并查集：假设我们要维护每个点的值 ，那么我们存储的是 使得 到根上所有点 的 之和就是原来的 。那么在找祖先时，我们先往父亲递归，然后将自己存储的值加上父亲的