English · Original
Chinese · Translation
Formal · Original
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.
Petya 和 Vasya 安排了一场游戏。游戏规则如下：玩家拥有一个包含 #cf_span[n] 个顶点和 #cf_span[m] 条边的有向图。其中一个顶点上放置了一个棋子，初始时棋子位于顶点 #cf_span[s]。玩家轮流沿图中的某条边移动棋子，Petya 先手。无法移动棋子的玩家输掉游戏。如果游戏持续了 #cf_span[106] 轮仍未分出胜负，则宣布平局。
Vasya 在游戏开始前一整夜都在进行“拼写与词性”的实验，因此在游戏一开始便睡着了。Petya 决定利用这一情况，同时代替自己和 Vasya 进行所有移动。
你的任务是帮助 Petya 判断他是否能获胜，或至少达成平局。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] —— 图中的顶点数和边数（#cf_span[2 ≤ n ≤ 105]，#cf_span[0 ≤ m ≤ 2·105]）。
接下来的 #cf_span[n] 行描述图的边信息。第 #cf_span[i] 行（#cf_span[1 ≤ i ≤ n]）包含一个非负整数 #cf_span[ci] —— 表示从顶点 #cf_span[i] 出发指向的顶点数量，以及 #cf_span[ci] 个互不相同的整数 #cf_span[ai, j] —— 这些目标顶点的编号（#cf_span[1 ≤ ai, j ≤ n]，#cf_span[ai, j ≠ i]）。
保证所有 #cf_span[ci] 的总和等于 #cf_span[m]。
下一行包含顶点编号 #cf_span[s] —— 棋子的初始位置（#cf_span[1 ≤ s ≤ n]）。
如果 Petya 能获胜，第一行输出 «_Win_»，第二行输出一个序列 #cf_span[v1, v2, ..., vk]（#cf_span[1 ≤ k ≤ 106]），表示 Petya 为获胜应访问的顶点序列。序列的首项 #cf_span[v1] 必须等于 #cf_span[s]，对于每个 #cf_span[i = 1... k - 1]，图中必须存在从 #cf_span[vi] 到 #cf_span[vi + 1] 的边，且顶点 #cf_span[vk] 必须没有出边。该序列需保证 Petya 获胜。
如果 Petya 无法获胜但能达成平局，则仅输出 «_Draw_»。否则输出 «_Lose_»。
第一个示例中的图如下：
初始时棋子位于顶点 #cf_span[1]。第一轮 Petya 将棋子移至顶点 #cf_span[2]，随后为 Vasya 移动至顶点 #cf_span[4]，接着再移至顶点 #cf_span[5]。此时轮到 Vasya，但他无合法移动，因此 Petya 获胜。
第二个示例中的图如下：
初始时棋子位于顶点 #cf_span[2]。Petya 唯一的合法移动是前往顶点 #cf_span[1]，随后他必须为 Vasya 移动至 #cf_span[3]。此时轮到 Petya，但他无合法移动，因此 Petya 失败。
第三个示例中的图如下：
Petya 无法获胜，但他可以沿着环移动，因此双方将达成平局。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m] —— 图中的顶点数和边数（#cf_span[2 ≤ n ≤ 105]，#cf_span[0 ≤ m ≤ 2·105]）。接下来的 #cf_span[n] 行描述图的边信息。第 #cf_span[i] 行（#cf_span[1 ≤ i ≤ n]）包含一个非负整数 #cf_span[ci] —— 表示从顶点 #cf_span[i] 出发指向的顶点数量，以及 #cf_span[ci] 个互不相同的整数 #cf_span[ai, j] —— 这些目标顶点的编号（#cf_span[1 ≤ ai, j ≤ n]，#cf_span[ai, j ≠ i]）。保证所有 #cf_span[ci] 的总和等于 #cf_span[m]。下一行包含顶点编号 #cf_span[s] —— 棋子的初始位置（#cf_span[1 ≤ s ≤ n]）。
## Output
如果 Petya 能获胜，第一行输出 «_Win_»，第二行输出一个序列 #cf_span[v1, v2, ..., vk]（#cf_span[1 ≤ k ≤ 106]），表示 Petya 为获胜应访问的顶点序列。序列的首项 #cf_span[v1] 必须等于 #cf_span[s]，对于每个 #cf_span[i = 1... k - 1]，图中必须存在从 #cf_span[vi] 到 #cf_span[vi + 1] 的边，且顶点 #cf_span[vk] 必须没有出边。该序列需保证 Petya 获胜。如果 Petya 无法获胜但能达成平局，则仅输出 «_Draw_»。否则输出 «_Lose_»。
[samples]
## Note
在第一个示例中，图如下：
初始时棋子位于顶点 #cf_span[1]。第一轮 Petya 将棋子移至顶点 #cf_span[2]，随后为 Vasya 移动至顶点 #cf_span[4]，接着再移至顶点 #cf_span[5]。此时轮到 Vasya，但他无合法移动，因此 Petya 获胜。
在第二个示例中，图如下：
初始时棋子位于顶点 #cf_span[2]。Petya 唯一的合法移动是前往顶点 #cf_span[1]，随后他必须为 Vasya 移动至 #cf_span[3]。此时轮到 Petya，但他无合法移动，因此 Petya 失败。
在第三个示例中，图如下：
Petya 无法获胜，但他可以沿着环移动，因此双方将达成平局。
**Definitions**
Let $G = (V, E)$ be a directed graph where:
* $V = \{1, 2, \dots, n\}$ is the set of vertices.
* $E \subseteq V \times V$ is the set of directed edges.
* $s \in V$ is the starting vertex.
* $\delta_{out}(u) = |\{v \in V \mid (u, v) \in E\}|$ denotes the out-degree of vertex $u$.
* A vertex $u$ is a **terminal vertex** (or sink) if $\delta_{out}(u) = 0$.
* A sequence of vertices $P = (v_1, v_2, \dots, v_k)$ is a **valid path** if $v_1 = s$ and $(v_i, v_{i+1}) \in E$ for all $1 \le i < k$. The length of the path is $L(P) = k-1$.
**Input Data**
1. Integers $n, m$ such that $2 \le n \le 10^5$ and $0 \le m \le 2 \cdot 10^5$.
2. For each $i \in \{1, \dots, n\}$: an integer $c_i$ followed by $c_i$ distinct integers $\{a_{i,j}\}$ representing the adjacency list, such that $\sum c_i = m$.
* Edges are defined as $E = \{(i, v) \mid i \in \{1, \dots, n\}, v \in \{a_{i,j}\}\}$.
3. Integer $s$ ($1 \le s \le n$).
**Objective**
Determine the outcome based on the existence of paths in $G$ starting from $s$, evaluated in the following strict priority order:
1. **Case: Win**
* **Condition:** There exists a valid path $P = (v_1, \dots, v_k)$ such that $v_k$ is a terminal vertex and $L(P) \equiv 1 \pmod 2$.
* **Output:** Print "Win", followed by the sequence of vertices $v_1, \dots, v_k$.
2. **Case: Draw**
* **Condition:** The condition for **Win** is not met, AND there exists a valid path starting at $s$ that contains a cycle (i.e., the path can be extended infinitely).
* **Output:** Print "Draw".
3. **Case: Lose**
* **Condition:** Neither the **Win** nor the **Draw** conditions are met (i.e., all valid paths starting at $s$ end at a terminal vertex with even length).
* **Output:** Print "Lose".
API Response (JSON)
{
"problem": {
"name": "D. Sleepy Game",
"description": {
"content": "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 i",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF937D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 i...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Petya 和 Vasya 安排了一场游戏。游戏规则如下：玩家拥有一个包含 #cf_span[n] 个顶点和 #cf_span[m] 条边的有向图。其中一个顶点上放置了一个棋子，初始时棋子位于顶点 #cf_span[s]。玩家轮流沿图中的某条边移动棋子，Petya 先手。无法移动棋子的玩家输掉游戏。如果游戏持续了 #cf_span[106] 轮仍未分出胜负，则宣布平局。\n\nVasya 在游戏开始前...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions**\nLet $G = (V, E)$ be a directed graph where:\n* $V = \\{1, 2, \\dots, n\\}$ is the set of vertices.\n* $E \\subseteq V \\times V$ is the set of directed edges.\n* $s \\in V$ is the startin...",
"is_translate": false,
"language": "Formal"
}
]
}