Election Promises

题意翻译

在Byteland，两个党派——WA党和TLE党，此时正在争夺席位。为了让更多公民给他们选票，他们都在不停地承诺降税。 Byteland有$n$个城市，$m$条单行道，并且不能从一个城市出发又回到这个城市。竞选开始前，第$i$个城市的税收是非负整数$h_i$。 一次拉票的过程：这个党派会来到一个城市$x$，承诺会将这个城市的税收**降低**为一个非负整数。同时，这个党派可以将从$x$走一条单行道可以直达的城市的税收做任意更改，变高变低都行，但还得保证该城市的税收是非负整数。 WA党会先进行一次拉票，然后TLE党进行，然后WA党进行，以此类推。无法执行一次拉票的党派会输。 假设两个党派都采用最优决策，如果WA党赢了，输出`WIN`，然后找出一种第一次拉票的方案，使得接下来TLE党必败，输出执行该方案后每个城市的税收情况。否则，输出`LOSE`。

题目描述

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?

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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.

题意翻译

在Byteland，两个党派——WA党和TLE党，此时正在争夺席位。为了让更多公民给他们选票，他们都在不停地承诺降税。 Byteland有$n$个城市，$m$条单行道，并且不能从一个城市出发又回到这个城市。竞选开始前，第$i$个城市的税收是非负整数$h_i$。 一次拉票的过程：这个党派会来到一个城市$x$，承诺会将这个城市的税收**降低**为一个非负整数。同时，这个党派可以将从$x$走一条单行道可以直达的城市的税收做任意更改，变高变低都行，但还得保证该城市的税收是非负整数。 WA党会先进行一次拉票，然后TLE党进行，然后WA党进行，以此类推。无法执行一次拉票的党派会输。 假设两个党派都采用最优决策，如果WA党赢了，输出`WIN`，然后找出一种第一次拉票的方案，使得接下来TLE党必败，输出执行该方案后每个城市的税收情况。否则，输出`LOSE`。