考虑将动态的删边过程，转化为静态的过程，尝试对于一个边的集合 $S$，判断从图中删除这个边集是否合法。我们将连接初始度数奇偶性相同的两个点的边称为红边，其他边称为蓝边。我们发现，按上述方法染色后，对于一个点，它被删除的邻边颜色按先后顺序写下来一定是 红，蓝，红，蓝，……。这里能给我们的边集是否合法的判断提供一个必要条件，即每个点相邻的红边不比蓝边少且至多多一。同时，这个条件也是充分的，我们在下面会给出构造方法。

现在考虑如何在满足上述条件的情况下，选出尽量大的边集。考虑建模费用流，对于一条连接左部点 $u$，右部点 $v$ 的边 $(u,v)$，如果它是红色，我们将网络图中连一条 $u\to v$ 的边，容量为 $1$，费用为 $-1$；否则连一条 $v\to u$ 的边，容量为 $1$，费用为 $-1$。对于左部点可能存在红边比蓝边多一的情况，所以需要连一条 $s\to u$ 的容量为 $1$，费用为 $0$ 的边来允许这种情况，同理右部点需要连一条 $v\to t$ 的容量为 $1$，费用为 $0$ 的边。连边 $t\to s$，容量为 $+\infty$，费用为 $0$，则无源汇最小费用可行流即是答案。

如何求出带负环的无源汇最小费用可行流？我们先强制负边满流，答案加上这些贡献，再删掉这些边，再加入用于退流的反向边，容量为原边容量，费用为原边取反。强制满流会导致某些点流量不平衡，需要使用上下界网络流的套路来求出正确答案。考虑定义 $f_i=in_i-out_i$，对于 $f_i>0$ 的入流量过多的点，连边 $S\to i$，费用为 $0$，流量为 $f_i$；对于 $f_i< 0$ 的出流量过多的点，连边 $i\to T$，费用为 $0$，流量为 $-f_i$。这样的连边方式其实就是增加了一些假的流量迫使在流量平衡后，多选一些入/出度的边来抵消原图的不平衡流量。最后只需跑一遍 $S\to T$ 的最小费用最大流即可。容易证明任意的合法流都能被这个连边方式取到。

下面给出最终答案的构造方式，同时也是第一段结论充分性的构造性证明。以下我们的图是指按照和网络流建图一样的定向方式将无向边定向成有向边之后的图。若我们在图中找到一个简单环（容易证明，存在环就一定存在简单环，并且可以用 dfs 的方式简单找出），那么我们删除这个环后，每个点的红边数减蓝边数肯定不会有变化，删除过程中只需保证每个点的红边比蓝边先删即可，这是容易的，一个简单的构造是先删光所有红边再删蓝边。那么我们并没有改变原图拥有的性质，将原图变成了无环的。那么我们现在只需每次找到一条极长的从零入度点（容易证明是左部点）开始的链，将其删去即可，删除方法依然是先删所有的红边再删蓝边，因为是 dag 所以链也一定是简单的，所以上述构造方法也是正确的。那么我们就做完了这道题。