← 返回题目列表

Codeforces · 936/B

B. 昏昏欲睡的游戏

中文机器翻译题面 查看原题

Petya 和 Vasya 安排了一场游戏。游戏按照以下规则进行。玩家有一个有向图,包括 n 顶点和 m 边缘。其中一个顶点包含一个芯片。最初芯片位于顶点 s。玩家轮流沿着图表的某些边缘移动筹码。佩蒂亚先走。无法移动筹码的玩家就输了。如果比赛持续 106 抽签结果轮流公布。

瓦夏在比赛前的晚上正在做“拼写和词性”的大型实验室工作,所以他在比赛一开始就睡着了。彼佳决定趁此机会,同时做出彼佳和瓦夏的举动。

你的任务是帮助 Petya 确定他是否能赢得比赛或至少打平。

输入

第一行输入包含两个整数 n 和 m — 图中的顶点数和边数 (2 ≤ n ≤ 105, 0 ≤ m ≤ 2·105).

下一个 n 行包含有关图形边缘的信息。 i- 第行 (1 ≤ i ≤ n) 包含非负整数 ci — 存在一条边的顶点数 i 到这些顶点并且 ci 不同的整数 ai, j — 这些顶点的索引 (1 ≤ ai, j ≤ n, ai, j ≠ i).

保证总和 ci 等于 m.

下一行包含顶点索引 s — 芯片的初始位置 (1 ≤ s ≤ n).

输出

如果 Petya 能赢得打印 «获胜» 在第一行。在下一行打印数字 v1, v2, ..., vk (1 ≤ k ≤ 106) — Petya 获胜时应访问的顶点序列。顶点 v1 应与 s。对于 i = 1... k - 1 应该有一个边缘 图中的 vi to vi + 1 。必须不可能从顶点移动 vk。顺序应该是 Petya 赢得比赛。

如果 Petya 无法获胜但可以打平,则打印 «抽奖» 在唯一的行中。否则打印 «失去».

示例

输入
复制

5 6
2 2 3
2 4 5
1 4
1 5
0
1

输出
复制

Win
1 2 4 5

输入
复制

3 2
1 3
1 1
0
2

输出
复制

Lose

输入
复制

2 2
1 2
1 1
1

输出
复制

Draw

注意

在第一个示例中,图表如下:

最初芯片位于顶点 1。在第一步中,Petya 将筹码移动到顶点 2,之后他将其移动到顶点 4 瓦夏。之后他移动到顶点 5。现在轮到瓦夏了,没有可能的行动,所以佩蒂亚赢了。

在第二个示例中,图表如下:

最初芯片位于顶点 2。 Petya 唯一可能的移动是到达顶点 1。之后他必须去 3 瓦夏。现在轮到佩蒂亚了,但他没有可能的行动,所以佩蒂亚输了。

在第三个示例中,图表如下:

Petya 无法获胜,但他可以沿着循环移动,因此玩家将打平。