CF1364D Ehab's Last Corollary
简单题。
特判掉 \(m = n - 1\) 的情况，此时一定能找到一个大小为 \(\left\lceil\frac{k}{2}\right\rceil\) 的独立集，二分图染色即可。
否则，我们建出 dfs tree，找到一条连接的两个端点深度之差最小的返祖边，设它为 \((u, v)\)，且 \(dep_u > dep_v\)。
若环长 \(c = dep_u - dep_v + 1 \le k\) 就完成任务了，否则 \(c > k\)，我们在环上隔一个点取一个点即可，这样可构成独立集。因为这是长度最小的环，所以中间不会再出现返祖边。
CF Gym 102900B Mine Sweeper II
感觉像脑筋急转弯。
考虑所有数字之和就是相邻的 \((\text{雷}, \text{空地})\) 对数，因此翻转后这个对数不会改变。
然后由于抽屉原理，\(b \to a\) 和 \(b \to \operatorname{inv}(a)\) 中至少有一个操作次数 \(\le \left\lfloor\frac{nm}{2}\right\rfloor\)，然后就做完了。
CF1391E Pairs of Pairs
建出 dfs 树，然后大胆把同深度的点配对。猜测是合法的，也可以证明一定合法。
那如果对数不够，我们发现深度 \(\ge \left\lceil\frac{n}{2}\right\rceil\)，然后直接拎出最深的结点和根的链即可。