这道题目是二分图博弈的板子
介绍一下二分图博弈：
设两部的节点分别为\(x_1,x_2,...,x_n\)和\(y_1,y_2,...,y_m\)，先手选择了\(x_i\)这个节点，则先手必胜当且仅当\(x_i\)是最大匹配的必须点（也就是说少了\(x_i\)的话最大匹配数会减少）
证明：
任选一个最大匹配，则\(x_i\)为匹配点，先手的策略是每次都选择\(x_i\)对应的匹配点\(y\)；在后手选择的时候，无论如何都不会选择到当前匹配下的非匹配的\(x\)，这是因为如果选择到了，比如说\(x_1-y_1-x_2-y_2-···-x_k\)，其中\(x_k\)不是当前匹配下的匹配点，那么我们可以让\(y_1\)匹配\(x_2\)，\(y_2\)匹配\(x_3\)，···，\(y_{k-1}\)匹配\(x_k\)从而获得一个匹配数不变的匹配而且不包含\(x_i\)，这与\(x_i\)为必须点矛盾，所以先手必胜
如果说先手选择了非必须点\(x_i\)，那么任选一个不包含\(x_i\)的最大匹配，先手走到的\(y\)一定是匹配点（否则存在增广路）；进一步由在当前匹配的情况下从\(x_i\)出发不存在增广路可知，后手策略为每次选择当前匹配下\(y\)的匹配点\(x\)即可，所以先手必败
至于寻找必须点，洛谷题解给了几种方法；我想到了一种，先随便找出一个最大匹配，然后枚举匹配点\(x\)，设其匹配点为\(y\)，那么我们考虑是否存在非匹配点\(x^{'}\)使得\(y\)与\(x^{'}\)之间有边，如果有的话就说明\(x\)不是匹配点（应该是正确的，但是还没有验证，正确性基于交错树分析吧）
标签：...,Planinarenje,匹配,COCI2017,选择,先手,2018 From： https://www.cnblogs.com/dingxingdi/p/18378936