Petya and Vasya arranged a game. The game runs by the following rules. Players have a directed graph consisting of _n_ vertices and _m_ edges. One of the vertices contains a chip. Initially the chip is located at vertex _s_. Players take turns moving the chip along some edge of the graph. Petya goes first. Player who can't move the chip loses. If the game lasts for 106 turns the draw is announced.
Vasya was performing big laboratory work in "Spelling and parts of speech" at night before the game, so he fell asleep at the very beginning of the game. Petya decided to take the advantage of this situation and make both Petya's and Vasya's moves.
Your task is to help Petya find out if he can win the game or at least draw a tie.
## Input
The first line of input contain two integers _n_ and _m_ — the number of vertices and the number of edges in the graph (2 ≤ _n_ ≤ 105, 0 ≤ _m_ ≤ 2·105).
The next _n_ lines contain the information about edges of the graph. _i_\-th line (1 ≤ _i_ ≤ _n_) contains nonnegative integer _c__i_ — number of vertices such that there is an edge from _i_ to these vertices and _c__i_ distinct integers _a__i_, _j_ — indices of these vertices (1 ≤ _a__i_, _j_ ≤ _n_, _a__i_, _j_ ≠ _i_).
It is guaranteed that the total sum of _c__i_ equals to _m_.
The next line contains index of vertex _s_ — the initial position of the chip (1 ≤ _s_ ≤ _n_).
## Output
If Petya can win print «_Win_» in the first line. In the next line print numbers _v_1, _v_2, ..., _v__k_ (1 ≤ _k_ ≤ 106) — the sequence of vertices Petya should visit for the winning. Vertex _v_1 should coincide with _s_. For _i_ = 1... _k_ - 1 there should be an edge from _v__i_ to _v__i_ + 1 in the graph. There must be no possible move from vertex _v__k_. The sequence should be such that Petya wins the game.
If Petya can't win but can draw a tie, print «_Draw_» in the only line. Otherwise print «_Lose_».
[samples]
## Note
In the first example the graph is the following:
<center></center>Initially the chip is located at vertex 1. In the first move Petya moves the chip to vertex 2, after that he moves it to vertex 4 for Vasya. After that he moves to vertex 5. Now it is Vasya's turn and there is no possible move, so Petya wins.
In the second example the graph is the following:
<center></center>Initially the chip is located at vertex 2. The only possible Petya's move is to go to vertex 1. After that he has to go to 3 for Vasya. Now it's Petya's turn but he has no possible move, so Petya loses.
In the third example the graph is the following:
<center></center>Petya can't win, but he can move along the cycle, so the players will draw a tie.
**Definitions:**
- Let $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $.
- Let $ \text{out}(v) $ denote the set of out-neighbors of vertex $ v $, i.e., $ \text{out}(v) = \{ u \mid (v, u) \in E \} $.
- Let $ s \in V $ be the initial vertex of the chip.
- Players alternate turns, starting with Petya. Petya controls both players’ moves.
- A player loses if they cannot move. After $ 10^6 $ moves, the game is a draw.
- Petya seeks to maximize his outcome: win > draw > lose.
**Given:**
- $ 2 \leq n \leq 10^5 $, $ 0 \leq m \leq 2 \cdot 10^5 $
- For each vertex $ i \in [1, n] $, the out-degree $ c_i = |\text{out}(i)| $ and the list of out-neighbors $ a_{i,1}, \dots, a_{i,c_i} $ are given.
- The total number of edges is $ \sum_{i=1}^n c_i = m $.
- Initial vertex $ s $.
**Objective:**
Determine the outcome of the game under optimal play by Petya (controlling both players), and if possible, output a winning sequence of at most $ 10^6 $ moves.
**Formal Analysis:**
Define the state of the game by the current vertex and whose turn it is. Since Petya controls both, the turn alternates but he chooses both moves. Thus, the game reduces to: Petya chooses a path $ v_1 = s, v_2, \dots, v_k $ such that $ (v_i, v_{i+1}) \in E $ for all $ i $, and:
- If $ v_k $ has no outgoing edges, Petya wins (opponent cannot move on their turn).
- If the path can be extended infinitely (i.e., contains a cycle), then Petya can force a draw.
- Otherwise, if all paths from $ s $ eventually lead to a dead end on Vasya’s turn (i.e., Petya is forced to move into a position from which the next move leads to a terminal state on his own turn), then Petya loses.
We use backward induction (like in combinatorial game theory) to classify vertices:
Define three states for each vertex $ v $:
- $ \text{Win}(v) $: if the player about to move from $ v $ can force a win (i.e., there exists a move to a vertex $ u $ such that $ \text{Lose}(u) $).
- $ \text{Lose}(v) $: if all moves from $ v $ lead to $ \text{Win}(u) $, i.e., opponent can always win.
- $ \text{Draw}(v) $: if no move leads to $ \text{Lose}(u) $, but at least one leads to $ \text{Draw}(u) $, and no move leads to $ \text{Win}(u) $.
But note: since Petya controls **both** moves, the turn structure is not alternating in the usual sense. Instead, the game is a single path chosen by Petya, and the loss condition is: **if the chip is on a vertex with no outgoing edges, then the player whose turn it is loses**.
Since Petya makes move 1, 3, 5, ..., and Vasya makes move 2, 4, 6, ..., the player who is to move on vertex $ v_i $ is:
- Petya if $ i $ is odd,
- Vasya if $ i $ is even.
Thus, Petya wins if he can force the chip to land on a vertex $ v_k $ with $ \text{out}(v_k) = \emptyset $ **and** $ k $ is even (so it’s Vasya’s turn to move and he cannot).
Petya loses if he is forced to move from a vertex with no outgoing edges (i.e., $ k $ odd and $ \text{out}(v_k) = \emptyset $).
Petya can draw if he can make a sequence of at least $ 10^6 $ moves without reaching a terminal state.
Thus, the problem reduces to:
1. **Find if there exists a path** $ s = v_1 \to v_2 \to \dots \to v_k $, $ k \leq 10^6 $, such that:
- $ \text{out}(v_k) = \emptyset $,
- $ k $ is even (so Vasya is to move and loses).
2. If not, check if there exists a **cycle reachable from $ s $** such that Petya can loop forever (i.e., draw).
3. Otherwise, all paths from $ s $ end in a terminal state on Petya’s turn → lose.
**Algorithm:**
We perform a BFS/DFS from $ s $, labeling each vertex with:
- `state[v] ∈ {Win, Lose, Draw}` — from the perspective of **the player who is to move** from vertex $ v $, assuming optimal play by both players (but since Petya controls both, we interpret this as: Petya can choose the path).
Wait — correction: Since Petya controls **both** moves, the game is deterministic and Petya chooses the entire path. So we don't need minimax. Instead:
- Petya can win if there exists a path $ s = v_1 \to v_2 \to \dots \to v_k $ with $ k $ even and $ \text{out}(v_k) = \emptyset $.
- Petya can draw if there exists a path from $ s $ that enters a cycle and can be extended to length $ \geq 10^6 $ without hitting a terminal vertex.
- Otherwise, Petya loses.
So we need:
1. **Check for winning path**: BFS from $ s $, tracking path length modulo 2. For each vertex $ v $, record the shortest even-length path to $ v $ that ends in a terminal state.
Specifically: We want to know if there exists a vertex $ v $ with $ \text{out}(v) = \emptyset $, and a path $ s \to \dots \to v $ of even length.
2. **Check for draw**: Is there a cycle reachable from $ s $ such that **no terminal vertex is reached on the path to the cycle**, and the cycle has length ≥ 1? Then Petya can loop indefinitely.
But note: even if there is a cycle, if all paths to cycles go through terminal states on odd steps, then Petya may be forced to lose before reaching the cycle.
So we must find: Is there a cycle $ C $ reachable from $ s $, and a path from $ s $ to $ C $ of length $ L $, such that for all vertices $ u $ on the path from $ s $ to $ C $, $ \text{out}(u) \neq \emptyset $, and $ C $ contains no terminal vertex? Then Petya can choose to enter the cycle and loop forever → draw.
3. Otherwise: every path from $ s $ eventually ends at a terminal vertex on an odd step → lose.
**Implementation Steps:**
- Precompute $ \text{out}(v) $ for each $ v $.
- Mark terminal vertices: $ \text{terminal}(v) \iff \text{out}(v) = \emptyset $.
- Use BFS/DFS to find:
a. **Winning condition**: Is there a vertex $ v $ with $ \text{terminal}(v) $, and the shortest path from $ s $ to $ v $ has **even** length?
- If yes → output "Win" and the path.
b. **Draw condition**: Is there a cycle in the graph reachable from $ s $, such that all vertices on the path from $ s $ to the cycle are non-terminal, and the cycle itself contains no terminal vertex?
- Use DFS to detect cycles in the subgraph of non-terminal vertices reachable from $ s $.
- If such a cycle exists → output "Draw".
c. Otherwise → "Lose".
**Note on path reconstruction:**
- For Win: store parent pointers during BFS (only on even steps to terminal nodes).
- For Draw: once a cycle is found, output a path of length $ \min(10^6, \text{path to cycle} + \text{cycle length} \cdot k) $.
**Final Formal Statement:**
Let $ G = (V, E) $, $ s \in V $, $ \text{out}(v) \subseteq V $ for each $ v \in V $.
Define:
- $ T = \{ v \in V \mid \text{out}(v) = \emptyset \} $
**Objective:**
- If $ \exists $ a path $ P = (v_1 = s, v_2, \dots, v_k) $, $ k \leq 10^6 $, such that:
- $ \forall i \in [1, k-1], (v_i, v_{i+1}) \in E $,
- $ v_k \in T $,
- $ k \equiv 0 \pmod{2} $,
then output "Win" and $ P $.
- Else if there exists a cycle $ C = (u_1, u_2, \dots, u_\ell, u_1) $, $ \ell \geq 1 $, such that:
- $ \forall u \in C, u \notin T $,
- $ \exists $ a path from $ s $ to $ u_1 $ of length $ L $, with all intermediate vertices $ \notin T $,
then output "Draw".
- Else output "Lose".