Addition-Subtraction Game

You and your friend are playing a 2 player game. The game is played in a graph of V vertices. The vertices are numbered from 0 to V − 1. The graph has some directed edges. But the graph does not contain any cycles or loops. The rule of the game is as follows.

Initially vertex i has a positive value valuei
Both players make their moves by turns. In his turn the player chooses a vertex with the following properties. • The value of the vertex is strictly positive. • The vertex has one or more outgoing edges. If there is no such vertex the player loses and the game terminates.
If the player can select a vertex the player will decrease the value of the selected vertex i by 1. Then from the set of vertices which have an incoming edge from vertex i, the player will select Ki (this value will be given as input) vertices and increase the value of those vertices by 1. Among these selected Ki vertices there can be duplicated vertices. And if a vertex is selected n times its value will be increased by 1 every time. Or in another word its value will be increased by n. For example if the Ki = 6 and the selected vertex set is {2,2,2,3,3,5} then value2 will be increased by 3, value3 will be increased by 2 and value5 will be increased by 1. Now consider the graph on the right. Let the values of K be {2,1,3,2}. Now the value set {0,0,0,5} is a losing terminating position because the player cannot select any vertex which have outgoing edges and positive values. For the value set {3,4,5,6} the current player can go to the following value states by 1 move. • {2,5,6,6} — K0 = 2. • {2,6,5,6} — K0 = 2. • {2,4,7,6} — K0 = 2. • {3,3,5,7} — K1 = 1. • {3,7,4,6} — • {3,6,4,7} — select the vertex 2, decrease its value by 1 and increase its adjacent 1 by 2 and 3 by 1. Here K2 = 3. select the vertex 0, decrease its value by 1. And increase both of 1 and 2 by 1. Here select the vertex 0, decrease its value by 1 and increase its adjacent 1 by 2. Here select the vertex 0, decrease its value by 1 and increase its adjacent 2 by 2. Here select the vertex 1, decrease its value by 1 and increase its adjacent 3 by 1. Here select the vertex 2, decrease its value by 1 and increase its adjacent 1 by 3. Here select the vertex 2, decrease its value by 1 and increase its adjacent 1 by 1 and 3 by 2. Here K2 = 3. K2 = 3. • {3,5,4,8} —

2/3 • {3,4,4,9} — select the vertex 2, decrease its value by 1 and increase its adjacent 3 by 3. Here K2 = 3. Now given the graph and initial values of each of the vertices your task is to determine if the first player wins or loses given that both players play perfectly. Input Input contains multiple number of test cases. First line contains T (1 ≤ T ≤ 20) the number of testcases. EachtestcasestartswithalineV (2≤V ≤100)andE(2≤E≤1500). V isthe number of vertices and E is the number of edges. Each of the next E lines contains 2 integers FROM (0 ≤ F ROM < V ) and T O (0 ≤ T O < V ) denoting that there is a directed edge from F ROM to T O. FROM and TO will not be equal. Also each vertex will have at most 15 outgoing edges. Next line contains V integers K0, K1, ..., KV −1. Each of the value of K is between 1 and 100 inclusive. Next line contains R (1 ≤ R ≤ 100) the number of rounds. There will be R round of game with this graph. Each of the next R lines contains the description of each round. Each round consists of V integers V alue0 V alue1 . . . V alueV −1 denoting the initial value of each vertex. Each of these V aluei will be between 1 and 100 inclusive. Output For each test case output consist of R + 1 lines. First line is ‘Game#i:’ where i is the game number. Game number starts from 1. Each of the next R lines contains ‘Round#j: RESULT’ where j is the number of round. RESULT is either ‘WINNING’ when the initial values of this round is a winning position for the first player or ‘LOSING’ when the initial values of this round is a losing position for the first player. We will assume that both players play perfectly. Print a blank line after the output of each test case. See the output for sample input for more clarification. Sample Input 2 33 10 20 12 022 5 300 410 501 111 222 43 01 12 23 3210 5 0000 0001 0010 0100 1000

3/3 Sample Output Game#1: Round#1: LOSING Round#2: WINNING Round#3: WINNING Round#4: WINNING Round#5: LOSING Game#2: Round#1: LOSING Round#2: LOSING Round#3: WINNING Round#4: WINNING Round#5: LOSING