Directed Graph Game with Infinite Play

Gennady and Georgiy are playing an interesting game on a directed graph. The graph has \(n\) vertices and \(m\) arcs (loops are allowed). A token is initially placed on one of the vertices. The players take turns moving the token along one of the arcs outgoing from the current vertex. If a player is unable to make a move (i.e. the token is at a vertex with no outgoing arcs) then that player loses.

The players have different preferences. Gennady (player 0) enjoys playing and would even prefer to prolong the game indefinitely rather than win, although winning is still better than losing. In other words his preference ordering is:

[ \text{Infinite play (Draw)} \succ \text{Win} \succ \text{Lose}. ]

On the other hand, Georgiy (player 1) does not wish to play forever. His preference ordering is:

[ \text{Win} \succ \text{Lose} \succ \text{Infinite play (Draw)}. ]

Both players know the other's preferences and play optimally. For a given initial vertex and the identity of the player who moves first, determine the outcome of the game. The possible outcomes are:

• Win: the player whose turn it is can force a win.
• Lose: the player whose turn it is will lose if both play optimally.
• Draw: the game will continue infinitely.

Note: In our analysis, each game state is defined as a pair \((v, p)\), where \(v\) is the current vertex and \(p\) is the player (0 for Gennady and 1 for Georgiy) whose turn it is. A terminal state (with no available moves) is a losing position for the moving player. When a move is made from state \((v, p)\) to \((u, 1-p)\), the outcome from the perspective of player \(p\) is the inversion of the outcome at \((u, 1-p)\); that is, if the outcome at \((u, 1-p)\) is Win then it becomes Lose for player \(p\), and vice‐versa, while an infinite play remains infinite.

Formally, if we encode outcomes as numbers from the perspective of the moving player (with values 0, 1, 2 corresponding to Lose, Win, and Draw respectively) then the inversion is defined as:

[ \operatorname{invert}(0)=1,\quad \operatorname{invert}(1)=0,\quad \operatorname{invert}(2)=2. ]

Furthermore, the optimal choices differ by player. When it is Gennady's (player 0) turn, his effective ordering is \(2 \succ 1 \succ 0\) (i.e. Draw > Win > Lose). When Georgiy (player 1) moves, his ordering is \(1 \succ 0 \succ 2\) (i.e. Win > Lose > Draw).

Your task is to determine, for each query consisting of an initial vertex and first player, what the outcome will be (printed as Win, Lose, or Draw).

Input Format

The input begins with a line containing two integers \(n\) and \(m\) \((1 \le n \le 10^5,\ 0 \le m \le 10^5)\) — the number of vertices and arcs, respectively. The vertices are numbered from 1 to \(n\).

Each of the next \(m\) lines contains two integers \(u\) and \(v\) denoting a directed arc from vertex \(u\) to vertex \(v\) (\(1 \le u,v \le n\)).

The next line contains a single integer \(q\) \((1 \le q \le 10^5)\) — the number of queries. Each of the following \(q\) lines contains two integers: a vertex \(s\) (the starting vertex) and a number \(p\) (either 0 or 1) indicating which player moves first (0 for Gennady, 1 for Georgiy).

Output Format

For each query, output a single line with one of the words "Win", "Lose", or "Draw", indicating the outcome of the game when both players play optimally.

inputFormat

First line: two integers \(n\) and \(m\).
Next \(m\) lines: each with two integers \(u\) and \(v\) (arc from \(u\) to \(v\)).
Next line: integer \(q\) (number of queries).
Next \(q\) lines: each with two integers: starting vertex \(s\) and player \(p\) (0 for Gennady, 1 for Georgiy).

outputFormat

For each query, output one line containing the result: "Win", "Lose", or "Draw".

sample

3 2
1 2
2 3
3
1 0
1 1
2 0

Lose
Win
Win

</p>