CF1149E.Election Promises

In Byteland, there are two political parties fighting for seats in the Parliament in the upcoming elections: Wrong Answer Party and Time Limit Exceeded Party. As they want to convince as many citizens as possible to cast their votes on them, they keep promising lower and lower taxes.

There are $n$ cities in Byteland, connected by $m$ one-way roads. Interestingly enough, the road network has no cycles — it's impossible to start in any city, follow a number of roads, and return to that city. Last year, citizens of the $i$-th city had to pay $h_i$ bourles of tax.

Parties will now alternately hold the election conventions in various cities. If a party holds a convention in city $v$, the party needs to decrease the taxes in this city to a non-negative integer amount of bourles. However, at the same time they can arbitrarily modify the taxes in each of the cities that can be reached from $v$ using a single road. The only condition that must be fulfilled that the tax in each city has to remain a non-negative integer amount of bourles.

The first party to hold the convention is Wrong Answer Party. It's predicted that the party to hold the last convention will win the election. Can Wrong Answer Party win regardless of Time Limit Exceeded Party's moves?

在比特兰（Byteland），有两大政党正为即将到来的大选争夺议会席位：错误答案党（Wrong Answer Party）和超时党（Time Limit Exceeded Party）。为了尽可能多地争取市民选票，两党不断承诺将税率一降再降。

比特兰共有 $n$ 座城市，由 $m$ 条单向道路连接。有趣的是，该道路网络中不存在环——即不可能从任意一座城市出发，沿若干条道路行走后回到起始城市。去年，第 $i$ 座城市的市民需缴纳 $h_i$ 比特兰元（bourles）的税款。

接下来，两党将轮流在不同城市举行竞选集会。若某政党在城市 $v$ 举行集会，则该政党必须将该城市的税率降至一个非负整数（单位：比特兰元）；同时，它还可任意调整所有能从 $v$ 经一条道路直接到达的城市的税率，唯一约束是：每座城市的税率仍须为非负整数。

首场集会由错误答案党举行。据预测，举行最后一场集会的政党将赢得大选。那么，无论超时党如何应对，错误答案党是否总能获胜？

The first line of the input contains two integers $n$, $m$ ($1 \leq n \leq 200\,000$, $0 \leq m \leq 200\,000$) — the number of cities and roads in Byteland.

The next line contains $n$ space-separated integers $h_1, h_2, \dots, h_n$ ($0 \leq h_i \leq 10^9$); $h_i$ denotes the amount of taxes paid in the $i$-th city.

Each of the following $m$ lines contains two integers ($1 \leq u, v \leq n$, $u \neq v$), and describes a one-way road leading from the city $u$ to the city $v$. There will be no cycles in the road network. No two roads will connect the same pair of cities.

We can show that the conventions cannot be held indefinitely for any correct test case.

输入的第一行包含两个整数 $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$ 的单向道路。道路网络中不存在环。任意两个城市之间至多只有一条道路相连。

我们可以证明：对于任意合法的测试用例，会议都无法无限期地举行下去。

If Wrong Answer Party can win the election, output WIN in the first line of your output. In this case, you're additionally asked to produce any convention allowing the party to win regardless of the opponent's actions. The second line should contain $n$ non-negative integers $h'_1, h'_2, \dots, h'_n$ ($0 \leq h'_i \leq 2 \cdot 10^{18}$) describing the amount of taxes paid in consecutive cities after the convention. If there are multiple answers, output any. We guarantee that if the party has any winning move, there exists a move after which no city has to pay more than $2 \cdot 10^{18}$ bourles.

If the party cannot assure their victory, output LOSE in the first and only line of the output.

如果“错误答案党”能够赢得选举，则在输出的第一行输出 WIN。在此情况下，你还需构造任意一种能使该党无论对手如何行动均能获胜的方案。第二行应包含 $n$ 个非负整数 $h'_1, h'_2, \dots, h'_n$（满足 $0 \leq h'_i \leq 2 \cdot 10^{18}$），表示实施该方案后各连续城市所缴纳的税额。若存在多种可行方案，输出任意一种即可。我们保证：只要该党存在必胜策略，则必存在一种策略，使得没有任何城市需缴纳超过 $2 \cdot 10^{18}$ 博尔勒的税款。

如果该党无法确保获胜，则在输出的第一行（也是唯一一行）输出 LOSE。

In the first example, Wrong Answer Party should hold the convention in the city $1$. The party will decrease the taxes in this city to $1$ bourle. As the city $2$ is directly reachable from $1$, we can arbitrarily modify the taxes in this city. The party should change the tax to $5$ bourles. It can be easily proved that Time Limit Exceeded cannot win the election after this move if Wrong Answer Party plays optimally.

The second example test presents the situation we created after a single move in the previous test; as it's Wrong Answer Party's move now, the party cannot win.

In the third test, we should hold the convention in the first city. This allows us to change the taxes in any city to any desired value; we can for instance decide to set all the taxes to zero, which allows the Wrong Answer Party to win the election immediately.

在第一个例子中，“错误答案党”应在城市 $1$ 举行大会。该党将把该城市的税率降低至 $1$ 博尔勒。由于城市 $2$ 可由城市 $1$ 直接到达，因此我们可以任意修改该城市的税率。“错误答案党”应将税率改为 $5$ 博尔勒。可以轻松证明：在此操作之后，若“错误答案党”采取最优策略，则“超时党”无法赢得选举。

第二个测试样例呈现了上一测试样例经过一次操作后所形成的情形；由于当前轮到“错误答案党”行动，该党无法获胜。

在第三个测试样例中，我们应在第一座城市举行大会。这使得我们能够将任意城市的税率修改为任意期望值；例如，我们可以决定将所有城市的税率均设为零，从而令“错误答案党”立即赢得选举。