太不牛了。
首先看到要求二分图上匹配条件，想到的就是在任意完美匹配上做调整，不难证明对于两种不同的完美匹配，若一种可以调整至解，那么另一种同样也可以调整至解。
随便找出一个完美匹配，如果黑边数是偶数直接数出即可，否则，从 dinic 反悔的角度上来看（我们姑且认为每条边都是有向边且 dinic 跑完一遍后本质上会将匹配中的边反向），调整就是找到残量网络中的一个黑边数为奇数的环，然后依次重新连接，本质上就是在描述匈牙利算法的反悔贪心过程。
此时问题便变得简单了，现在就是求一张图中黑边数量为奇数的环，利用扩展域并查集的思路就是拆奇点偶点建图，本质上就是跑若干个连通块，时间复杂度 \(O(n + m)\)，瓶颈在网络流。
写起来比较吃大分。