In Byteland, there are two political parties fighting for seats in the Parliament in the…
- User
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
The first line of the input contains two integers n, m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000) — the number of cities and roads in Byteland.
The next line contains n space-separated integers h_1, h_2, ..., h_n (0 ≤ h_i ≤ 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 ≤ u, v ≤ n, u ≠ 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
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, ..., h'_n (0 ≤ h'_i ≤ 2 ⋅ 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 ⋅ 10^{18} bourles.
If the party cannot assure their victory, output LOSE in the first and only line of the output.
Examples
Input
4 2 2 1 1 5 1 2 3 4
Output
WIN 1 5 1 5
Input
4 2 1 5 1 5 1 2 3 4
Output
LOSE
Input
3 3 314 159 265 1 2 1 3 3 2
Output
WIN 0 0 0
Input
6 4 2 2 5 5 6 6 1 3 2 4 3 5 4 6
Output
LOSE
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.
Assistant
We are given a directed acyclic graph (DAG) with n nodes, m edges. No cycles. Two players alternate making moves. A move consists of choosing a node v, then setting the tax value of v to some non-negative integer (any value), and also for each node u that is directly reachable from v by a single edge (i.e., out-neighbors), we can arbitrarily set their taxes to any non-negative integer. All other nodes keep their current values. The move must produce a configuration where all taxes are non-negative integers.
The starting configuration is given by h_i. The first player is Wrong Answer Party. They want to force a win: they want to be the player who makes the last move (i.e., after some move, no further moves are possible? Wait: "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." So it's a normal play impartial game? Actually, not impartial because moves are defined on a configuration. Players alternate moves. The player who cannot move loses? Let's interpret: "It's predicted that the party to hold the last convention will win the election." So if a player makes a move and after that move, the opponent cannot make a move (i.e., no city can be chosen such that we can modify taxes legally? But a player can always choose any city? Possibly they can always choose any city, but the move might be forced to modify taxes to something? The rules: 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.
Important: They can modify the taxes of v and its immediate out-neighbors arbitrarily. They are not forced to change them? They "can arbitrarily modify", meaning they have freedom to set them to any non-negative integer. So they can choose any non-negative integers for v and all out-neighbors. But they must "decrease the taxes in this city"? Actually: "the party needs to decrease the taxes in this city to a non-negative integer amount of bourles." The phrasing "decrease" might imply they must set it to some value, not necessarily lower than before? Actually "decrease" means they must set it to a non-negative integer, but the starting tax is non-negative, so they could set it to the same? Typically in such game "decrease" indicates they must set it to a smaller value? Let's check the examples: In first example, initial taxes: 2 1 1 5. Move: choose city 1, set its tax to 1 (decreased from 2 to 1), and set city 2's tax to 5 (increased!). So they increased the neighbor. So "decrease" is probably not a requirement; they just set it to some amount, could be any non-negative. But the phrase "decrease the taxes" is confusing. Actually reading: "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." It says "decrease" but then says "to a non-negative integer amount". In example, they indeed decreased from 2 to 1. Could they have increased? That would not be a decrease. So maybe they must set v's tax to a non-negative integer that is strictly less than its current value? However they also can modify neighbors arbitrarily; neighbors can be set to any non-negative, no requirement to decrease. The word "decrease" appears in the statement: "they keep promising lower and lower taxes." So perhaps each convention in a city forces them to lower the tax in that city (they promise lower tax). So the move: pick a node v; set h_v to any non-negative integer strictly less than its current value. For all out-neighbors u (directly reachable by one road), set h_u to any non-negative integer (no restriction). Other nodes unchanged.
Is that the rule? Let's test with examples. In first example: h_1=2, they set to 1 (decrease), h_2 can be set arbitrarily, they set to 5 >1. That fits.
In third example: initial 314 159 265; they pick city 1, then they set city 1 to 0 (decrease) and out-neighbors are 2 and 3 (since edges 1->2,1->3). They set both to 0. That is allowed: decrease city 1 to 0, set neighbors to 0. That yields 0 0 0. Then after that, is the game over? If the opponent cannot move, then Wrong Answer wins. Let's see if opponent can move from all zeros. If all taxes are 0, can they pick a city? If they pick city v, they must decrease its tax to a non-negative integer strictly less than current. Since current is 0, the only non-negative integer less than 0 is none. So they cannot make a move. So indeed the game ends and the last mover (first player) wins. So that matches.
In second example: after the move from first example, configuration is 1 5 1 5. It says LOSE for Wrong Answer if it is their turn. Let's analyze: with taxes 1 5 1 5, can the player (Wrong Answer) make a move to force win? Suppose they pick city 2 (tax 5) could decrease it to something lower, say 0; and modify its out-neighbors? City 2 has no outgoing edges? Actually graph: edges 1->2 and 3->4. So city 2 has no outgoing edges. So they could only change city 2. After setting city 2 to 0, we get 1 0 1 5. Then opponent could perhaps pick city 4 (tax 5) and set it to 0, getting 1 0 1 0. Then can player move? They could pick city 1 (tax 1) set to 0, leaving 0 0 1 0. Then opponent could pick city 3 (tax 1) set to 0, leaving all zeros and then player cannot move? Wait turn order: after player move, opponent moves, etc. Let's simulate: start config: 1 5 1 5, player (Wrong) to move. He wants to be last mover. But LOSE suggests from that position it's losing for the player to move. So indeed it might be a losing position. So the rule seems consistent: you must decrease the chosen node strictly.
Thus the game: Given a DAG with n nodes, each node has a non-negative integer value (tax). A move: choose a node v; set h_v to any value h'_v such that 0 ≤ h'_v < h_v (strictly decreasing). For each out-neighbor u of v (i.e., u such that there is a directed edge v->u), set h_u to any non-negative integer (could be any, including higher, lower, same) arbitrarily. All other nodes unchanged. The move must produce a configuration with all non-negative integers. Players alternate. The player who cannot make a move loses (normal play). Determine if first player has a winning strategy from initial configuration, and if so, output a winning move (the resulting configuration after his move). Output any such configuration that leads to a position where whatever opponent does, first player can eventually win.
Observations: This is a combinatorial impartial? But not impartial because move options may depend on the values and graph. But we can analyze the game as a variant of a take-away game on heaps possibly with dependencies.
Given it's a DAG, we might compute Grundy numbers? But the ability to arbitrarily set out-neighbors makes it unusual. Essentially, when you pick a node v, you can set v to any lower value, and you can completely reset its children to any values you like. This can be seen as: the move can "reset" the subtree (but only immediate children, not deeper) to any values. But because later moves can affect deeper nodes indirectly, we need to consider the whole DAG.
Goal: Determine winning position and a winning move.
Constraints up to 200k nodes, edges. Need efficient solution.
We need to understand structure of game.
Let's formalize: state is vector h ∈ ℕ^n. Move: choose v; pick a new value x_v with 0 ≤ x_v < h_v. For each u in Out(v) (direct successors), pick any y_u ∈ ℕ. Update these values.
Terminal state: when all h_v = 0? Because if any node has h_v > 0, you could choose it and decrease it (since you can always set it to 0? Actually you need strictly less, so if h_v > 0, you can set to 0, as 0 < h_v if h_v >0. So any node with positive value can be chosen and decreased to 0 (or lower). So the only condition for a move to exist is that there exists a node with h_v > 0. Because if all are 0, no node can be decreased. So terminal positions are exactly those where all h_i = 0. So losing position for player to move when all zeros.
Thus the game ends when all taxes are zero. The players alternate decreasing some nodes and possibly increasing others (but only children of the chosen node). Wait increasing children could make non-zero values from zero, thus possibly create new moves. So you could increase some nodes from 0 to positive, which adds moves. So it's not simply decreasing overall.
But note: when you pick a node v, you must decrease v itself. So v's value strictly goes down. Children can be set arbitrarily high. So you could create new positive values.
This resembles a game where each node has a "pile" and you can move by reducing a pile and resetting its followers arbitrarily. This is reminiscent of the "turn the lights out" or "Dawson's Kayles"? Not exactly.
Maybe we can convert to impartial game using the concept of "minimum excludant" if the graph is a rooted tree? But it's a DAG, possibly with multiple parents. However the graph is acyclic, so we can topologically sort.
Because children can be set arbitrarily, effectively, after a move at v, the values of its out-neighbors can be set to any values we like, independent of previous values. That means we can "control" the state of those nodes. So from the perspective of game theory, after moving at v, the values of children are completely under our control; we can choose them optimally to force a win.
Thus the move at v allows us to set the entire "subgame" consisting of the children (and their descendants) to any desired state? Not exactly: only immediate children values can be set arbitrarily, but deeper nodes remain unchanged unless affected via future moves that may start from children. However, since we can set children to any non-negative integer, we can effectively decide the "starting" values for those nodes. So we can treat the children's subtrees as independent subgames with values we can set arbitrarily. But note that the children may have outgoing edges to further nodes; those further nodes are not directly set by our move, they keep their current values. However, if we set a child to some value, that child can later be chosen, and its own children can then be set arbitrarily, etc. So the state of the whole graph can be thought of as separate components? But the graph may have dependencies; still, the ability to arbitrarily set children values gives a lot of power.
This game might be equivalent to a Nim heap on each node but with the rule that when you reduce a heap to some value, you can replace the heaps of its children with any Nim heaps. Actually resembles the game of "Dawson's Kayles"? Not exactly.
Let's think in terms of impartial combinatorial game theory: The game can be expressed as the disjunctive sum of independent subgames? The graph structure may cause interactions. However, the ability to set children arbitrarily might decouple them if we think in terms of Grundy values of each node. Since when you make a move on a node v, you can change the Grundy values of its children to anything you want (since you set their actual values, which determine Grundy). So perhaps we can assign a Grundy number to each node based on its current tax value and the structure of its descendants. But note that the value of a node influences the moves on it, and the values of its children influence moves on them. If we could compute the nimber of the whole game as some function of each node, maybe the game is equivalent to Nim on some set of independent heaps? Let's explore.
Define for each node v, a function f(v, h_v) that gives the Grundy value of the subgame consisting of the whole graph? Not independent because moves on one node affect children which are also nodes. However, the graph is a DAG, so the game might be a "poset game" where you remove elements? But here we don't remove, we adjust numbers.
Another angle: Could the outcome be determined solely by the parity of the sum of something? Maybe it's equivalent to Nim where each node's tax value is considered as a heap of size equal to the Grundy number of the node's "mex" of children? But we need to derive.
Let's try to analyze small cases.
Case with no edges (m=0). Then each node is independent. Move: choose a node v, set its value to any smaller non-negative integer. That's just a Nim heap of size h_v (since you can reduce it to any lower number, like a Nim heap where you can move to any smaller heap). Actually in Nim, you can reduce a heap to any smaller size, so that's exactly a Nim heap. So the game is just the sum of n independent Nim heaps. So the Grundy of a heap of size h is h (since Nim heap of size h has Grundy h). So the overall Grundy is XOR of all h_i. First player wins iff XOR != 0. Winning move: choose a heap where h_i has the most significant bit, and reduce it to h_i XOR totalXOR, making XOR zero. So that's simple.
Now consider a simple graph: one edge from u to v (u -> v). So nodes: u (with value a), v (value b). Moves:
- Move on u: can decrease u to any a' < a, and can set v to any non-negative integer (say c). So after move, state (a', c).
- Move on v: can decrease v to any b' < b; no outgoing edges from v (or maybe v has none), so only change v. So move on v is like a Nim heap on v.
Thus the game is like: v is a Nim heap. u is a special node that can be reduced and also can set v arbitrarily.
This is reminiscent of the game where one heap can "replace" another. In impartial game terms, the Grundy of position (a,b) may be something like mex of options.
Let's compute Grundy values for small a,b (assuming no other nodes). Let g(a,b) be Grundy for this two-node DAG with edge u->v.
Terminal: a=0,b=0 => Grundy 0.
We can compute recursively.
Define options from move on u: for any a' from 0 to a-1, and any c (non-negative integer), the resulting Grundy is g(a',c). Move on v: for any b' from 0 to b-1, resulting Grundy is g(a,b').
We need to compute Grundy as mex of all resulting Grundies from options.
But note c can be any non-negative integer; thus from move on u we can achieve any state (a',c) with a'<a and c arbitrary. That includes states with any Grundy value that can be realized as g(a',c). So the set of Grundy numbers reachable by moving on u is the set of all Grundy numbers that appear as g(a',c) for some a'<a, c≥0.
Similarly, move on v yields states g(a,b') for b'<b.
Thus we need to find pattern.
Let's compute small a,b.
First, consider a=0: then u cannot be chosen because h_u=0 (must be >0 to move). So only moves possible are on v if b>0. So g(0,b) = mex of {g(0,b') for 0≤b'<b} if b>0, else 0. This is just Nim heap on b: g(0,b) = b. Since from b=0 =>0; b=1: options {g(0,0)=0} => mex{0}=1; b=2: options {0,1} => mex{0,1}=2; etc. So g(0,b)=b.
Now for a>0.
We'll compute for a=1.
g(1,b): Options:
- Move on u: choose a'<1 => a'=0 only. And any c ≥0. So we can achieve any state (0,c) where c arbitrary. Their Grundy = g(0,c)=c. So we can achieve any non-negative integer Grundy value (since c can be any integer). So the set of Grundy numbers reachable via move on u is ℕ (all non-negative integers).
- Move on v: if b>0, we can move to (1, b') for b'<b. Their Grundy numbers are g(1,b') for b'<b.
Now Grundy g(1,b) = mex( S ), where S = {all integers from u-move} ∪ {g(1,b') for b'<b}.
Since u-move yields all non-negative integers, S contains all integers (since ℕ is all numbers). Then mex of S would be? The set S includes all non-negative integers (since u-move gives every integer). Then mex is the smallest non-negative integer not in S, but if S = ℕ, then mex is undefined? Actually mex of ℕ (all natural numbers) is the next integer, which would be infinite? But Grundy numbers are normally finite. However in combinatorial games, if you can move to any Grundy number, then the mex of an infinite set containing all non-negative integers would be the smallest non-negative integer not present; but if all are present, then there is none, so the mex would be some infinite ordinal? That can't happen in a finite impartial game; but our game might have infinite options if c can be arbitrarily large, leading to Grundy numbers that can be arbitrarily large. So it's possible that from a position, you can move to positions with arbitrarily large Grundy numbers, making the mex not finite. But typically, Grundy numbers are defined as mex of a set of Grundy numbers from options; if the set includes all natural numbers, the mex would be the smallest natural number not in the set, but if all are present, then mex is the smallest limit ordinal? That would be infinite. But in impartial combinatorial games with infinite options, Grundy numbers can be infinite. However, in standard combinatorial game theory, Grundy numbers are natural numbers only if the game is "short" (no infinite loops) and the set of options is finite? Actually, the definition of mex for a set of non-negative integers: mex(S) = smallest non-negative integer not in S. If S contains all non-negative integers, then there is no smallest non-negative integer not in S; but by convention, mex of a set containing all naturals is the smallest infinite ordinal? But Nim-heaps are usually finite; but here the option set is infinite because c can be any arbitrarily large integer, leading to arbitrarily large Grundy numbers (since g(0,c)=c). So indeed from state (1,b), via move on u, you can achieve any Grundy value (since you can set c to any integer, and g(0,c)=c). So the set of Grundy numbers from u-move is all non-negative integers. Therefore S contains all naturals. Then mex(S) would be undefined in the naturals. That suggests that the Grundy number of (1,b) is not a finite integer. But the game is finite? The game cannot go on forever because each move reduces some value? However we can increase values on children. But we must decrease the chosen node. Could the game be infinite? The statement says: "We can show that the conventions cannot be held indefinitely for any correct test case." So the game is guaranteed to terminate in a finite number of moves regardless of play. That implies that the game is acyclic in terms of some measure; it is a finite impartial game. The existence of infinite options doesn't prevent finiteness of play as long as each move reduces some well-founded measure. Here, when we move on u, we decrease u, but can increase v arbitrarily. So the measure that ensures termination is not simply sum of values, because you could increase v. But they claim it's always finite. Let's reason: The graph is acyclic; maybe we can define a potential function such as sum over nodes of h_i * (some topological order weight) that strictly decreases? Let's try: assign each node a number like 2^{-depth}? Not integer. Since h_i can increase, it's tricky. However the statement assures termination: "We can show that the conventions cannot be held indefinitely for any correct test case." So it's a finite game. In a finite game, the Grundy number is a non-negative integer (by the Sprague-Grundy theorem for impartial games that are finite and normal-play). The set of options is finite? Actually the game state space might be infinite because taxes can become arbitrarily large (since you can set children arbitrarily high). But the game is guaranteed to terminate regardless of choices; that means from any state, there is no infinite play. However the state space might be infinite, but the game graph from a given starting state might be finite? Actually from a given initial state, because you can increase values arbitrarily, could there be infinite branches? Possibly you could keep increasing values in cycles? But the DAG has no cycles, so you cannot increase a node that later leads back to itself? But you could increase a node's child, then later decrease that child, then later increase it again via its parent? Example: u->v. Starting with (1,0). Player moves on u: decrease u to 0, set v to 1000. Now state (0,1000). Next player moves on v: decrease v to something, but cannot increase u because v has no outgoing to u. So v's value goes down. Then later if player moves on u again? u is 0, cannot move. So from (0,1000), only moves on v, which strictly decrease v. So eventually v reaches 0. So the game terminates. What about a longer chain? You could increase a node, then later a move on its parent could increase it again? But to move on parent, parent must have positive value. In the chain a->b->c. Suppose we have state (1,0,0). Player 1 moves on a: can set a to 0, set b to 1000. State (0,1000,0). Player 2 moves on b: decreases b to some value, set c to arbitrary, say 2000. State (0, 500, 2000). Player 1 moves on c: can only decrease c (no children) to 0. State (0,500,0). Player 2 moves on b: decrease b to some value, set c arbitrary again, etc. This could continue? Note that each time we move on b, we decrease b (strictly). So b's value strictly decreases each time b is chosen. So b can only be chosen finitely many times (since its value is non-negative integer and decreases each time). Similarly, a can only be chosen when its value >0; after it becomes 0, it's stuck. c can be chosen many times but each time it decreases; however c can be increased by moves on b, so c can be reset to high values. So c could be increased many times, but each time b is chosen, b decreases, and b is a node that can only be chosen a finite number of times (since its value cannot increase? Actually b can be increased only if its parent a is chosen, but after a becomes 0, a cannot be chosen again. So b can only be increased at most the number of times a is chosen, which is finite because a decreases each time and becomes 0. So b's value is bounded in the sense that the number of times it can be increased is limited by the number of times its ancestors are chosen. So overall, the game should be finite. So the state space from a given start may be infinite (since we could set children to arbitrarily large numbers), but any play will terminate because each node can only be increased a finite number of times (depending on the number of times its ancestors are chosen, which is limited by the initial values of those ancestors). So there is a finite bound on the total number of moves, though the values can become large.
Given that the game is finite, the Sprague-Grundy theorem applies even if the set of options from a state is infinite, as long as the game is short (no infinite plays). The Grundy value is defined as the mex of the set of Grundy values of options. This set may be infinite. mex of an infinite set of natural numbers can be finite if the set does not include all naturals. For example, the set of even numbers has mex=1. So it's possible that the set of reachable Grundy numbers from a state is not all naturals. In our case, from (1,b) via move on u, we can achieve any state (0,c) with c arbitrary, so we can achieve any Grundy number g(0,c)=c. So the set includes all non-negative integers. So indeed, from (1,b), the set S contains all natural numbers (via u-move) and also the Grundy numbers from v-move. So S = ℕ ∪ {g(1,b') for b'<b}. Since ℕ already includes all numbers, S = ℕ (if we consider ℕ includes all non-negative integers). Then mex(ℕ) is the smallest natural not in ℕ? That doesn't exist. So the Grundy number would be undefined as a natural number. But the Sprague-Grundy theorem requires Grundy numbers to be defined for all positions in an impartial game. So if a position can move to positions with arbitrarily large Grundy numbers and includes all naturals, then the mex would be the first infinite ordinal? In combinatorial game theory, if the set of options is infinite, the mex is still defined as the smallest ordinal not in the set. So the Grundy number could be an infinite ordinal (like ω). But then the game is not a disjunctive sum of Nim heaps? However, the statement that the game always terminates suggests that the game graph is well-founded but may have infinite branching. Grundy values can be transfinite ordinals in some contexts, but typically for impartial games with finite play, Grundy numbers are nimbers which are elements of the set of all ordinals? Actually in combinatorial game theory, for impartial games that are "loopy" or with infinite options, the theory extends to "nimbers" which are the values of impartial games; they are the ordinals under mex? But usually for normal-play impartial games, the Grundy numbers are elements of the set of non-negative integers if the game is finite and options are finite. For games with infinite options, the Sprague-Grundy theorem generalizes to the "mex" of a set of ordinals, giving possibly infinite ordinals. However, such games might not be equivalent to Nim heaps of finite size. But here we are asked only to determine winning/losing, not necessarily compute Grundy. Winning positions are those where the Grundy number (nimber) is non-zero. For transfinite nimbers, non-zero means not 0. But is it possible that Grundy numbers become infinite? Let's test with the simple 2-node DAG.
We computed g(0,b)=b. Now for a=1, the set of Grundy numbers reachable from u-move is all natural numbers (since for any c, we get g(0,c)=c). So that set is ℕ. The set from v-move is {g(1,b') : b' < b}. So the set S = ℕ ∪ T, where T is some finite set of numbers (maybe). Since ℕ already contains all natural numbers, S = ℕ. mex(ℕ) is ω (the smallest infinite ordinal). So g(1,b) = ω for all b? But then what about g(1,0)? Options: u-move gives all naturals, v-move none (since b=0). So S = ℕ, mex = ω. So g(1,0)=ω. g(1,1): u-move gives ℕ, v-move to (1,0) gives ω. So S = ℕ ∪ {ω}. mex of that set? The smallest ordinal not in the set: all naturals are in ℕ, ω is in the set, so next is ω+1? Actually ordinals: 0,1,2,... ω, ω+1,... So the smallest ordinal not in ℕ∪{ω} is ω+1 (since all finite numbers are in ℕ, ω is present, so ω+1 is not). So mex would be ω+1. So g(1,1)=ω+1. Similarly g(1,2): options from v: g(1,0)=ω, g(1,1)=ω+1, plus u-move gives ℕ. So S contains all naturals, ω, ω+1. mex = ω+2. So it seems g(1,b) = ω+b. That suggests Grundy numbers can be infinite ordinals.
Now what about a=2? Let's try to compute g(2,b). Options from u: choose a'<2 (0 or 1) and any c. So we can achieve any state (0,c) giving Grundy c, and any state (1,c) giving Grundy g(1,c) = ω+c. So from u-move we can achieve all natural numbers (c) and all ω+c. That set is all ordinals less than ω+ω? Actually ordinals: naturals 0,1,2,..., and also ω, ω+1, ω+2,... So we can achieve all ordinals < ω+ω (i.e., ω2) except possibly some? For any natural n, we get n. For any ordinal of form ω + n, we can get by choosing a'=1 and c=n. So we get all ordinals less than ω+ω (i.e., up to but not including ω+ω). Also we could get possibly a'=0 and c infinite? c is natural, so only finite. So the set from u-move is all ordinals < ω+ω (i.e., all ordinals less than ω2). Options from v: moves to (2, b') for b'<b, whose Grundy we don't know yet.
So g(2,b) = mex( S ∪ T ), where S = all ordinals < ω2, T = {g(2,b') : b'<b}. Since S already contains all ordinals less than ω2, the mex will be at least ω2. Then depending on T, it might be higher. So likely g(2,b) = ω2 + b, similarly.
Thus by induction, for a DAG that is just a chain of nodes? Actually for a node with outgoing edge to a child, the Grundy seems to be something like ω * a + h_child? But careful: In our two-node case, node u has a child v. The Grundy of state (a,b) might be ωa + b? Let's test: For a=1,b=0: ω1+0 = ω, matches. For a=1,b=1: ω+1, matches. For a=2,b=0: ω2? But earlier we hypothesized g(2,0) might be ω2? Let's compute: from u-move we can achieve all ordinals < ω2. So mex of that set is ω2 (since ordinals < ω2 are exactly those less than ω2; the smallest ordinal not in that set is ω2). So g(2,0)=ω2. That fits ω2+0. For a=2,b=1: u-move gives all < ω2; v-move gives g(2,0)=ω2. So S = (<ω2) ∪ {ω2}. mex = ω2+1. So g(2,1)=ω2+1. So indeed pattern: g(a,b) = ωa + b.
Check a=0: ω*0+b = b, matches.
Thus for two nodes with edge u->v, the Grundy value of the state is ω*a + b, where a = h_u, b = h_v. This is an ordinal sum.
Now consider a more complex DAG. Could the Grundy value be expressed as an ordinal that is a sum over nodes of something like ω^{depth} * value? Possibly the game is equivalent to Nim on heaps where each node corresponds to a Nim heap of size h_i multiplied by some "weight" that depends on the structure (like the number of different paths?).
Observation: The move on node v allows you to set all its children arbitrarily. In ordinal terms, that means you can change the Grundy contributions of the children to any ordinal you want (subject to constraints). If the overall Grundy is something like the Nim-sum (or ordinal sum?) of contributions, then moving on v corresponds to reducing its own contribution and setting children's contributions arbitrarily. That resembles the game of "Hackenbush" or "Green Hackenbush"? Actually in impartial Hackenbush on a rooted tree, each edge contributes a value like a binary expansion? But here we have numbers, not just 0/1.
Alternatively, we can think in terms of the concept of "turning turtles" or "poset games" where each node has a "value" that is an ordinal, and the overall value is the XOR? Not XOR, but maybe the sum (nim-heap) of these ordinals? In the two-node case, the Grundy of the whole position is ωa + b, which is not simply the sum of a and b (like a+b) nor XOR. But note that ωa + b can be seen as the ordinal sum: a copies of ω, plus b. In ordinal arithmetic, ωa is defined as a * ω (ordinal multiplication: ω * a = ω+ω+... a times). But is it additive? ωa = ω × a? Actually ω * a (with a natural number) equals ω·a = ω+ω+...+ω (a times) which is ω·a. But note that ω + ω = ω·2, not ω^2. So our expression ω*a + b is exactly ω·a + b. That's an ordinal less than ω^2? Since ω·a + b < ω·(a+1) ≤ ω^2 if a is finite. So Grundy values are ordinals below ω^2.
For larger DAG, perhaps Grundy values are ordinals less than ω^k for some depth k. Since the DAG is finite and acyclic, its longest path length is bounded. The ordinal might be represented in Cantor normal form with ω powers corresponding to topological levels.
Consider a chain of three nodes: 1->2->3, with values a,b,c. Let's try to compute Grundy g(a,b,c). By similar reasoning, we might get g = ω^2 * a + ω * b + c? Let's test small values manually to see pattern.
We have nodes: u (value a) -> v (value b) -> w (value c). Edges: u->v, v->w. Move on u: decrease a to a' < a; can set v to any value b' (non-negative integer) arbitrarily; w unchanged? Actually immediate out-neighbors of u are only v. So after move on u, we set v arbitrarily, but w stays as before. So state becomes (a', b', c). Where b' is chosen arbitrarily, c unchanged.
Move on v: decrease b to b' < b; can set w to any c' arbitrarily; u unchanged.
Move on w: decrease c to c' < c; no children, so only c changes.
Thus we can compute Grundy by recursion.
Hypothesis: g(a,b,c) = ω^2 * a + ω * b + c (ordinal addition and multiplication). Let's test for a=1,b=0,c=0.
Compute via definition.
We need to find Grundy for state (1,0,0). Options:
- Move on w: none since c=0.
- Move on v: b=0, so cannot move.
- Move on u: a=1 >0, can set a'=0 (only), and set b' to any integer (say x). So resulting state (0, x, 0). Grundy g(0,x,0) should be? According to hypothesis, g(0,x,0) = ω^20 + ωx + 0 = ω * x. So we can achieve any Grundy of form ω * x, for any non-negative integer x. Also we can set b' to something, c remains 0. So reachable Grundy numbers: all multiples of ω, i.e., 0, ω, ω·2, ω·3, ... . That's all ordinals less than ω^2 that are multiples of ω (i.e., ω·k). Are there any other options? No.
Thus from (1,0,0), the set S of Grundy numbers of options is { ω·k | k ∈ ℕ }.
Now what is mex of this set? The set includes 0, ω, ω·2, ω·3, ... . The ordinals less than ω^2 are of the form ω·a + b, with a,b natural. The set S contains exactly those with b=0. The smallest ordinal not in S is? 0 is in S, 1 is not. But is 1 less than ω^2? Yes, 1 = ω·0+1. Since 1 is not in S, mex(S) = 1? But wait mex is defined as the smallest ordinal not in the set. The set S contains 0, ω, ω·2, ... . Among ordinals, the usual ordering: 0 < 1 < 2 < ... < ω < ω+1 < ... So 1 is not in S, so mex would be 1. However, our hypothesis predicted g(1,0,0) = ω^21 + ω0 + 0 = ω^2. That is much larger than 1. So maybe our hypothesis is wrong; maybe the Grundy is not that simple.
But note: the options from moving on u gave states (0,x,0) with Grundy = ? We need to compute g(0,x,0) properly. Let's compute g(0,b,c) for chain of two nodes? Actually with three nodes, but if a=0, then node u is dead. Then we have a subgraph with nodes v->w, with values b and c. That's exactly the two-node case we already solved, where Grundy = ωb + c. So g(0,b,c) = ωb + c. Indeed, for b=x, c=0, g(0,x,0) = ω*x + 0 = ω·x. So that matches.
Now S = { ω·x | x ∈ ℕ }.
Now what is mex of S? The ordinals: 0,1,2,..., ω, ω+1,... The smallest ordinal not in S is 1, because 1 is not of the form ω·x. So mex(S) = 1. That would imply g(1,0,0)=1. But is that consistent with other options? Are there any other moves? v and w cannot move because b=0,c=0. So only move is u. So indeed the set of options Grundy numbers is exactly the set of all multiples of ω. mex of that set is 1. So g(1,0,0)=1.
Wait, but earlier in two-node case, g(1,0) was ω, not 1. That's because there was no deeper node. So the Grundy value depends on the structure depth. For a chain of length 2 (u->v), we had g(1,0)=ω. For chain of length 3 (u->v->w), g(1,0,0) appears to be 1. That is interesting. So the Grundy value is not simply ω^depth * value.
Let's compute more for chain of length 3.
General g(a,b,c) for chain u->v->w.
We have base: when a=0, g(0,b,c) = ω*b + c (since two-node chain). Let's denote that as G_two(b,c).
Now for a>0, moves:
- Move on u: choose a' < a, set v to any b', w unchanged. So state becomes (a', b', c). Grundy = g(a',b',c). Since a' can be any integer from 0 to a-1, and b' any integer ≥0.
- Move on v: choose b' < b, set w to any c', u unchanged. State (a, b', c'). Grundy = g(a,b',c').
- Move on w: choose c' < c, state (a,b,c').
We need to compute g(a,b,c). This seems more complex.
Let's attempt to compute small values systematically to see pattern.
First, we have g(0,b,c) = ω*b + c.
Now compute g(1,0,0). As argued, options from u: a'=0, b' any, c=0 => g(0,b',0) = ω*b'. So reachable Grundy = {ω * k | k≥0}. Also moves on v? b=0 => none. moves on w? c=0 => none. So S = {0, ω, 2ω, 3ω, ... }. mex = 1. So g(1,0,0)=1.
Now g(1,0,1): a=1,b=0,c=1. Options:
- Move on u: a'=0, b' any, c=1 => state (0,b',1) => Grundy = ωb' + 1. So reachable Grundy = { ωk + 1 | k≥0 }.
- Move on v: b=0 => none.
- Move on w: c=1 => can set c' =0 (since decrease). state (1,0,0) => Grundy = 1 (as computed). So also get Grundy 1. So S = { ωk + 1 for all k≥0 } ∪ {1}. That's all numbers of the form ωk+1. Notice ωk+1 includes 1 when k=0? ω0+1 =1, so it's included anyway. So S = { ωk + 1 | k≥0 }. What ordinals are not in S? The smallest ordinals: 0,2,3,...? 0 is not in S (since all are of the form ωk+1, which for k=0 is 1, for k≥1 are at least ω, so 0 is missing). So mex(S) = 0? Wait mex is smallest non-negative ordinal not in S. 0 is not in S, so mex = 0. But is that correct? Actually 0 is not in S, so g(1,0,1)=0. That would be a losing position. Let's check manually: Starting with (1,0,1). Is it a P-position? Possibly yes. So g(1,0,1)=0.
Now g(1,1,0): a=1,b=1,c=0. Options:
- Move on u: a'=0, b' any, c=0 => state (0,b',0) => Grundy = ωb'. So reachable {ωk}.
- Move on v: b=1 => can set b'=0 (only), and set w to any c' (since out-neighbor w). So state (1,0,c') => Grundy = g(1,0,c'). We need g(1,0,c') for any c' (c' any non-negative). We have g(1,0,0)=1, g(1,0,1)=0, and we might compute others.
- Move on w: c=0 => none.
So we need to compute g(1,0,c') for all c'. Let's try to compute general g(1,0,c). We have a=1,b=0,c variable. Options:
- Move on u: a'=0, b' any, c unchanged => (0,b',c) => Grundy = ωb' + c. So reachable all ordinals of form ωk + c.
- Move on w: decrease c to c'<c => (1,0,c') => Grundy = g(1,0,c') recursively. So g(1,0,c) is mex of set S_c = { ω*k + c | k≥0 } ∪ { g(1,0,c') for c' < c }. We can compute by induction on c.
We already have: c=0: S_0 = { ωk + 0 } ∪ {} = {ωk}. mex = 1. So g(1,0,0)=1. c=1: S_1 = { ωk + 1 } ∪ { g(1,0,0)=1 } = { ωk+1 } ∪ {1} = same set. mex: smallest ordinal not in set is 0? Check 0? 0 not in set. So g(1,0,1)=0. c=2: S_2 = { ωk + 2 } ∪ { g(1,0,0)=1, g(1,0,1)=0 } = { ωk+2 } ∪ {0,1}. So set contains 0,1,2? Actually ωk+2 for k=0 gives 2, so 2 is in set. So we have 0,1,2, and all numbers of the form ωk+2 for k≥1 which are >= ω+2, etc. So the smallest missing ordinal is? 0,1,2 present; next is 3. So mex = 3? But check if 3 is in the set? ωk+2 never equals 3 for integer k because ωk for k≥1 is infinite, and for k=0 it's 2. So 3 not in set. Also maybe from the recursive part we have only 0 and 1. So 3 is not present. So mex = 3. Thus g(1,0,2)=3. c=3: S_3 = { ωk+3 } ∪ {0,1,3? Actually g(1,0,0)=1, g(1,0,1)=0, g(1,0,2)=3} so we have {0,1,3} and also numbers ωk+3 for k≥0. For k=0, 3 is included. So set contains 0,1,3, and all ωk+3 (k≥1). Missing smallest: 2 is not in set? Check: is 2 present? From ωk+3, k=0 gives 3; k=1 gives ω+3, etc. Not 2. Recursive part gives 0,1,3. So 2 missing. So mex=2. So g(1,0,3)=2. c=4: S_4 = { ωk+4 } ∪ {0,1,3,2? Actually g(1,0,0..3): 0:1,1:0,2:3,3:2 => set {0,1,2,3}. plus {4, ω+4,...}. So we have 0,1,2,3,4 present. Next missing is 5? Check 5 not present (since ωk+4 gives 4, ω+4, etc). So mex=5? But also need to see if any from recursive gives 5? No. So mex=5. So g(1,0,4)=5. c=5: S_5 = { ω*k+5 } ∪ {0,1,2,3,5? Actually from previous: 0:1,1:0,2:3,3:2,4:5 => set {0,1,2,3,5}. plus {5, ω+5,...} includes 5. So we have 0,1,2,3,5. Missing 4. So mex=4. So pattern: g(1,0,c) seems to be: if c even? Let's list: c:0->1,1->0,2->3,3->2,4->5,5->4,... So it's like: if c is even, g = c+1; if c is odd, g = c-1. That is: g(1,0,c) = c xor 1? Actually c XOR 1: 0 xor1=1, 1 xor1=0, 2 xor1=3, 3 xor1=2, yes. So g(1,0,c) = c xor 1. Interesting.
Thus g(1,0,c) = c^1.
Now back to g(1,1,0). We have:
- u-move: { ω*k } for k≥0.
- v-move: b=1: can set b'=0, and set w to any c' (arbitrary). So resulting state (1,0,c') with Grundy = g(1,0,c') = c' ^ 1. Since c' can be any non-negative integer, we can achieve any integer that is of the form x xor 1? But as c' ranges over all naturals, c'^1 ranges over all naturals (since xor with 1 is a bijection on naturals? Actually it is a permutation: for each natural n, there is exactly one c' such that c'^1 = n: c' = n^1. So the set of Grundy numbers from v-move is all natural numbers (including 0,1,2,...). Because for any n, choose c' = n^1, then Grundy = n. So v-move can achieve any non-negative integer.
Thus S = { ω*k (k≥0) } ∪ ℕ (all naturals). So S contains all naturals and all multiples of ω. The smallest ordinal not in S? All naturals are present (0,1,2,...), so the first missing ordinal is ω? But ω is present? ω is a multiple of ω (k=1), so ω is in S. Next is ω+1? ω+1 is not in the set (since naturals are finite, multiples of ω are of the form ω·k, which are infinite ordinals; ω+1 is not a multiple of ω, and it is not a finite natural because naturals are finite. So ω+1 is not in S. So mex = ω+1. So g(1,1,0) = ω+1.
That is interesting: For chain of length 3, g(1,1,0) = ω+1. Compare to two-node case where g(1,0)=ω and g(1,1)=ω+1. So the presence of an extra node w (child of v) seems to transform the Grundy values: Instead of g(u,v) = ω*a + b, we get something more complex.
Let's try to compute g(1,1,1) to see pattern: a=1,b=1,c=1. Options:
- u-move: (0,b',1) => Grundy = ωb' + 1. So reachable { ωk + 1 }.
- v-move: (1,0,c') with c' arbitrary => Grundy = c' ^ 1 (as above). So reachable all naturals.
- w-move: c=1 => can set c'=0 => (1,1,0) Grundy = ω+1.
So S = { ωk+1 } ∪ ℕ ∪ {ω+1}. Since ℕ includes 0,1,2,...; ωk+1 includes 1, ω+1, ω·2+1, etc. ω+1 is already included maybe from ℕ? No ω+1 is not a natural. But it is included from u-move? For k=1, ω1+1 = ω+1, so yes from u-move. So S = ℕ ∪ { ωk+1 for all k } = ℕ ∪ (all ordinals of the form ωk+1). Since ℕ already includes all finite numbers. So the set contains all naturals, and all ordinals ωk+1 for k≥1? For k=0, ω0+1=1 is natural, so covered. So S = ℕ ∪ { ω+1, ω·2+1, ω·3+1, ... }. So what ordinals are missing? The smallest ordinal not in ℕ is ω. But ω is not in S? Check: ω is not a natural, and is it of form ωk+1? For k=1, ω+1; for k=0,1; no. So ω is missing. So mex = ω? But is ω in the set from v-move? v-move gives naturals, not ω. u-move gives ω*k+1, not ω. So ω is not present. So mex(S) = ω. Thus g(1,1,1) = ω.
Interesting. So Grundy values for chain of length 3 are not simply linear.
The game seems complex. However, perhaps we don't need full Grundy analysis; we only need to determine if the starting position is winning for first player, and produce a winning move if so. Since n,m up to 200k, we need an efficient algorithm.
The statement says: "We can show that the conventions cannot be held indefinitely for any correct test case." So the game is finite. The output requires either WIN and a configuration after first move, or LOSE.
This problem likely has a known solution. Let's think about it more abstractly.
We have a DAG. Moves: pick a node v, reduce its value, and arbitrarily reassign values to all its immediate children. This is reminiscent of the game of "Turning Turtles" or "Dawson's Kayles" but not exactly.
Another viewpoint: Consider the values as representing some kind of "nim-heap" at each node, but with the ability to "reset" children. This might be equivalent to playing Nim on the "grundy numbers" of each node, but the grundy number of a node depends on the values of its children. Perhaps we can compute for each node a "value" (like a nim-heap size) that depends only on its current tax and the values of its children? In combinatorial game theory, there is a concept of "poset games" where you remove a node and all nodes greater than it. But here it's different.
Maybe we can reframe the game as a "take-away" game on a rooted tree (or DAG) with "toll" values. Another approach: Since players can set children arbitrarily, they can effectively "control" the game from those children onward. So after a move on v, the player can set the children's values to any numbers, which presumably can be chosen to be "winning" or "losing" positions for the opponent. But note: After the move, it's the opponent's turn. So when you move on v, you can choose the values of its children to force the overall position to be losing for the opponent (i.e., a P-position). So the question reduces to: can the first player choose some node v and some new values for v and its children such that the resulting position is a P-position (losing for the next player). If yes, then first player wins.
Thus we need to characterize P-positions (losing positions) in this game. Then the first player wins if the initial position is not a P-position, and can move to a P-position.
So the problem reduces to computing the outcome (N or P) for a given state, and also producing a move to a P-position.
So we need to compute the set of positions that are losing. This is like solving a impartial game with infinite moves.
We can attempt to derive a characterization. Let's denote the whole state as a function h: V -> ℕ. The move definition.
Define a function F from states to {P,N}. Terminal state (all zeros) is P (since player to move cannot move, so it's losing). Then a state is N if there exists a move leading to a P-state; else it's P.
Given the infinite branching (setting children arbitrarily