考虑把棋盘黑板染色，然后给这个二分图跑最大匹配
某位置开始后手必胜，当且仅当存在一个最大匹配使得这个点不是匹配点
证明：若存在，则先手每次只需要走到上个点对应的匹配点，最终一定是后手无路可走；若不存在，则起始点旁边必定都是匹配点，先手走上去转化成存在的情况
所以问题变成了求二分图最大匹配必经点
考虑左部点，对于每个非匹配边，从左到右连有向边，对于匹配边，从右到左连有向边，那么从每个非匹配左部点开始遍历，遍历到的所有左部点都不是必经点（因为走出了一条交替路，所有匹配边变非匹配边，非匹配边变匹配边，那匹配点也全边非匹配点了）
对于右部点同理
其他：二分图