二分图博弈
* 基本局面：
* 两个玩家轮流行动，每次面临一个二分图 G=(V,E)G=(V,E)G=(V,E) 和它的一个顶点 u∈Vu\in Vu∈V 构成的局面 (G,u)(G,u)(G,u)。一名玩家的行动是必须选择一个与 uuu 相连的点 vvv，随后将顶点 uuu 以及其所有关联边从图中删去，得到新图 G′G'G′ 并将新局面 (G′,v)(G',v)(G′,v) 给到另一个玩家。如果某位玩家在其回合开始时，无法选择相连的点就输了
* 结论：
* 游戏先手必胜，当且仅当顶点 uuu 是图的 GGG 最大匹配关键点，也就是说，在图 GGG 的所有最大匹配中，顶点 uuu 都是匹配点。
* 证明：
* 我们设 GGG 的一个匹配为 MMM。
* <1>假如现在局面顶点 uuu 是图的 GGG 最大匹配关键点，要求先手移动到的点 vvv 也在 MMM 中。然后残余图 G′G'G′ 的最大匹配最大为 ∣M∣−1|M|-1∣M∣−1 ，我们称 G′G'G′ 的这个匹配为 M′M'M′，显然其为残余图的最大匹配，其变化是去掉了一条边，也就是说现在 vvv 在 M′M'M′ 不匹配了，此时顶点 vvv 不是图的 GGG 最大匹配关键点。
* <2>假如现在局面存在最大匹配 MMM 使得 uuu 未被匹配，显然此时 uuu 相连的点均在最大匹配中被匹配，转移到的点在最大匹配中，在残余图里因为 vvv 不被匹配匹配上 uuu 的情况消失了，所以一定有一个 vvv 是图的 G′G'G′ 最大匹配关键点
* 根据博弈论的小性质（详见Nim游戏大学习那篇文章的课后作业），可以证明了。
* 推广：
* 先手在博弈中选择起点
* 先手必败当且仅当 GGG 存在完美匹配
* 证明与上文同理
* 对于一般图也成立
* [NOI2011] 兔兔与蛋蛋游戏
* 超全的板子
* 正常写就行了，注意代码里的注释
*
