CF1149E Election Promises

在 Byteland，有两个政党正在为即将到来的议会选举争夺席位：Wrong Answer Party 和 Time Limit Exceeded Party。为了让尽可能多的市民投票支持自己，他们不断承诺降低税收。 Byteland 有 $n$ 个城市，通过 $m$ 条单向道路连接。有趣的是，道路网络中没有环——也就是说，不可能从某个城市出发，经过若干条道路后又回到该城市。去年，第 $i$ 个城市的市民需要缴纳 $h_i$ bourles 的税。 现在，两个政党将轮流在不同的城市举行竞选集会。如果某个政党在城市 $v$ 举行集会，该党需要将该城市的税收降低到某个非负整数。同时，他们可以任意修改所有可以通过一条道路从 $v$ 直接到达的城市的税收。唯一的限制是，每个城市的税收都必须保持为非负整数。 Wrong Answer Party 首先举行集会。预计最后举行集会的政党将赢得选举。无论 Time Limit Exceeded Party 如何行动，Wrong Answer Party 能否确保获胜？

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 200\,000$，$0 \leq m \leq 200\,000$），分别表示 Byteland 的城市数和道路数。 第二行包含 $n$ 个用空格分隔的整数 $h_1, h_2, \dots, h_n$（$0 \leq h_i \leq 10^9$），其中 $h_i$ 表示第 $i$ 个城市去年的税收。 接下来的 $m$ 行，每行包含两个整数（$1 \leq u, v \leq n$，$u \neq v$），表示一条从城市 $u$ 到城市 $v$ 的单向道路。道路网络中不会有环，也不会有两条道路连接同一对城市。 可以保证，对于任何合法的测试用例，集会的进行不会无限持续下去。

如果 Wrong Answer Party 能确保获胜，输出第一行为 WIN。此时，你还需要输出一组能够确保该党获胜的集会方案。第二行应包含 $n$ 个非负整数 $h'_1, h'_2, \dots, h'_n$（$0 \leq h'_i \leq 2 \cdot 10^{18}$），表示集会后各城市的税收。如果有多种答案，输出任意一种即可。保证如果该党有必胜方案，则存在一种方案使得所有城市的税收均不超过 $2 \cdot 10^{18}$。 如果该党无法确保获胜，则输出第一行且仅有一行 LOSE。

在第一个样例中，Wrong Answer Party 应该在城市 $1$ 举行集会，将该城市的税收降为 $1$。由于城市 $2$ 可以直接从 $1$ 到达，因此可以任意修改该城市的税收。该党应将其税收改为 $5$。可以证明，如果 Wrong Answer Party 采取最优策略，Time Limit Exceeded Party 无法获胜。 第二个样例展示了在上一个样例中经过一次操作后的局面；此时轮到 Wrong Answer Party 行动，该党无法获胜。 在第三个样例中，应在第一个城市举行集会，这样可以将任意城市的税收修改为任意值。例如，可以将所有城市的税收都设为 $0$，Wrong Answer Party 可以立即获胜。 由 ChatGPT 4.1 翻译