Election Promises
Contest: Codeforces Round 556 (Div. 1)
Difficulty rating: 3200
Tags: games, graphs

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?

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4 2
2 1 1 5
1 2
3 4

Example output:
WIN
1 5 1 5

Example input:
4 2
1 5 1 5
1 2
3 4

Example output:
LOSE

Editorial:
Let's get straight to the main lemma:
Lemma. For any vertex $$$v$$$, let's define the level of $$$v$$$ as $$$M(v) = \mathrm{mex}\,\{M(u)\,\mid\,v\to u\,\text{is an edge}\}$$$ where $$$\mathrm{mex}$$$ is the minimum-excluded function. Moreover, for any $$$t \in \mathbb{N}$$$, let $$$X(t)$$$ be the xor-sum of the taxes in all cities $$$v$$$ fulfilling $$$M(v) = t$$$; that is, $$$X(t) = \bigoplus\,\{h_v\,\mid\,M(v)=t\}$$$. The starting party loses if and only if $$$X(t) = 0$$$ for all $$$t$$$'s; that is, if all xor-sums are equal to 0.
Proof. Let's consider any move from the position in which all xor-sums are zero. If we're holding the convention in the city $$$v$$$, then we must decrease the amount of taxes in this city. Note however that there is no direct connection from $$$v$$$ to any other city $$$u$$$ having the same level as $$$v$$$, as $$$M(v)$$$ is the smallest integer outside of the set $$$\{M(u)\,\mid\,v\to u\,\text{is an edge}\}$$$. Therefore, there is exactly one tax value changing at level $$$M(v)$$$, and thus the value $$$X(M(v))$$$ must change. As it was zero before, it must become non-zero.
Now consider any configuration where some xor-sums are non-zero. Let $$$t$$$ be the highest level at which $$$X(t) > 0$$$. We want to hold the election in a selected city at level $$$t$$$. Which one? Notice that no city at a single level is connected to each other, and therefore we can only afford to pick one city and strictly decrease its tax. This is equivalent to the game of Nim where each city corresponds to a single stack of stones. We perform a single optimal move in this game: pick a city and decrease the tax in the city by a non-zero amount of bourles, leading to the position where the new xor-sum of the taxes at this level $$$X'(t)$$$ is equal to zero. We also need to take care of zeroing all $$$X(l)$$$'s for $$$l < t$$$. This is however straightforward: for each $$$l < t$$$, pick a single city $$$v_l$$$ fulfilling at level $$$l$$$ directly reachable from $$$v$$$ (there must be one from the definition of $$$M(v)$$$), and alter the value of tax in order to nullify $$$X(l)$$$.
The proof above is actually constructive and allows us to compute a single winning move in $$$O(n + m)$$$ time.
As a small bonus: if you're into advanced game theory, you can come up with the lemma above without much guesswork. One can compute the nimbers for the state where there are no taxes anywhere except a single city $$$v$$$ where the tax is equal to $$$h_v$$$, and it turns out to be equal to $$$\omega^{M(v)} \cdot h_v$$$ where $$$\omega$$$ is the smallest infinite ordinal number. Moreover, it's not that hard to see that the nimber for the state where there are more taxed cities is a nim-sum of the nimbers corresponding to the states with only one taxed city. This all should quite naturally lead to the lemma above.