题目链接（Luogu 翻译）

给定一个左右各 个点的有向二部图，没有重边，且没有双向边。

A(lice) 和 B(ob) 在这个图上玩一个游戏，Ta 们轮流操作，直到图中只有 个点，从 A(lice) 开始：

1. A(lice) 可以从右部选择一个点并删掉；
2. B(ob) 可以从左部选择一个点并删掉。

设最终左部剩下的点为 ，右部最终剩下的点为 ，若：

1. 存在从 到 的边，则 A(lice) 赢；
2. 存在从 到 的边，则 B(ob) 赢；
3. 和 之间不存在边，则平局。

假定双方均采取最优策略，问 A(lice) 的最优策略是？

注：最优策略指，若存在必胜策略，则应用必胜策略；否则，若存在平局策略，则使用平局策略。

---

第一个结论，A(lice) 必胜当且仅当右部中存在一个点的入度为 。

条件的充分性显然，下证其必要性。

考虑局面的补图，则必胜条件变为右部存在一个点的度数为零。因此只需说明，对于一个右部点度数均非零的局面，B(ob) 可以维持这个性质。

例如，若此时两侧各 个点，A(lice) 操作后，左侧有 个点，右侧有 个点，只考虑右侧度数为 的点，不会超过 个，因此左侧总有一个点没有与度数为 的点相连，B(ob) 只需要删除这个点即可。

---

第二个结论，A(lice) 不输当且仅当右部存在一个点的出度为 。充分性显然，必要性与结论一证明类似。

---

综合两个结论，若通过结论一判断 A(lice) 必胜，则问题解决，A(lice) 有必胜策略；否则，若通过结论二判断 A(lice) 不输，则 A(lice) 有平局策略；否则，A(lice) 必败。