← 返回题目列表

Codeforces · 1149/E

E. 选举承诺

中文机器翻译题面 查看原题

在Byteland,有两个政党在即将到来的选举中争夺议会席位:错误答案党和超时党。由于他们希望说服尽可能多的公民为他们投票,因此他们不断承诺降低税收。

Byteland 有 $$$n$$$ 个城市,由 $$$m$$$ 单向道路连接。有趣的是,道路网络没有循环——不可能从任何城市出发,沿着多条道路行驶,然后返回该城市。去年,第 $$$i$$$ 个城市的公民必须缴纳 $$$h_i$$$ 布尔税。

政党现在将在各个城市轮流举行选举大会。如果一方在$$$v$$$城市举行大会,则该一方需要将该城市的税收减少到非负整数布尔。然而,同时他们可以任意修改使用单条道路从 $$$v$$$ 可以到达的每个城市的税收。必须满足的唯一条件是每个城市的税收必须保持非负整数布尔值。

第一个召开大会的政党是错误答案党。预计举行最后一次代表大会的政党将赢得选举。无论超时一方如何行动,错误答案一方能否获胜?

输入

输入的第一行包含两个整数 $$$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$$$ 的单向道路。道路网络中不会有自行车。没有两条道路会连接同一对城市。

我们可以证明,对于任何正确的测试用例,约定不能无限期地举行。

输出

如果错误答案党能够赢得选举,请在输出的第一行输出 WIN。在这种情况下,您还需要制定任何约定,无论对手的行为如何,都可以让一方获胜。第二行应包含 $$$n$$$ 非负整数 $$$h'_1, h'_2, \dots, h'_n$$$ ($$$0 \leq h'_i \leq 2 \cdot 10^{18}$$$) 描述会议后连续城市缴纳的税额。如果有多个答案,则输出任意一个。我们保证,如果一方有任何获胜的举动,则存在一个举动,之后没有城市必须支付超过 $$$2 \cdot 10^{18}$$$ 布尔斯。

如果一方不能确保胜利,则在输出的第一行也是唯一一行中输出 LOSE。

示例

输入 #1

4 2
2 1 1 5
1 2
3 4

输出 #1

WIN
1 5 1 5

输入 #2

4 2
1 5 1 5
1 2
3 4

输出 #2

LOSE

输入 #3

3 3
314 159 265
1 2
1 3
3 2

输出 #3

WIN
0 0 0

输入#4

6 4
2 2 5 5 6 6
1 3
2 4
3 5
4 6

输出#4

LOSE

注意

在第一个例子中,错误答案党应该在$$$1$$$城市举行大会。该党将把这个城市的税收降低到 $$$1$$$ bourle。由于从$$$1$$$可以直接到达城市$$$2$$$,所以我们可以任意修改这个城市的税收。该党应该将税收改为$$$5$$$ bourles。很容易证明,如果错误答案党发挥最佳,则超过时间限制在这一步之后就无法赢得选举。

第二个示例测试呈现了我们在上一个测试中单步移动后创建的情况;由于现在是错误答案党的举动,该党无法获胜。

第三次测试,我们应该在第一个城市举行大会。这使我们能够将任何城市的税收更改为任何想要的值;例如,我们可以决定将所有税收设置为零,这使得错误答案党立即赢得选举。