← 返回题目列表

AtCoder · code_festival_2015_okinawa_d

D. Shiritori 游戏词典

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

问题

在一个国家 N 正在使用不同种类的字符,有一个字典包含 M 条目,每个条目都是一个单词的定义。所有种类的字符都列为字符 1,字符 2, ..., 字符 N。的 i_{th} 该词典的条目(作为单词)以字母开头 p_i,并以字母结尾 q_i.

Cat Snuke 和 Wolf Sothe 将使用这本字典来玩一个名为 知鸟 。 (请注意,本游戏中的 Shiritori 与普通的 Shiritori 游戏不同。)

  • 第一个动作将由 Cat Snuke 进行,然后两名玩家将交替移动。
  • 对于第一步,玩家必须依次说出以字符开头的单词 1。如果没有任何以字符开头的单词 1,玩家又输了。
  • 对于其余的动作,该回合的玩家必须说出以字典中上一个动作中所说的单词的最后一个字符开头的任何单词。如果没有任何合适的词,玩家就输了。
  • 任何单词都可以说任意多次 .

应该有一些字典说两个玩家即使竭尽全力也无法改变游戏的结果。对于这些字典,在这种情况下,我们想知道第一个玩家或第二个玩家是否会获胜,甚至游戏永远不会停止。

将给出字典中的所有单词。我们可以假设这两名球员会尽力而为。请决定第一位玩家(Cat Snuke)或第二位玩家(Wolf Sothe)是否会获胜,否则游戏将永远不会停止。


输入

输入将通过以下格式的标准输入给出。

N M
p_1 q_1
p_2 q_2
:
p_M q_M
  • 在第一行,一个整数 将给出 N(1≦N≦100,000)、M(1≦M≦200,000) 。
  • 从第二行开始有 M 行代表本词典中的所有单词。 i_{th} 行,整数 p_i(1≦p_i≦N) 和 q_i(1≦q_i≦N) 将由空格给出。

可能存在以相同字符开头和以相同字符结尾的不同单词。 p_i = p_j 和 q_i = q_j 即使当 i \neq j.

输出

假设两名玩家会尽力而为。输出 Snuke 如果第一个玩家获胜,则输出 Sothe 如果第二个玩家在一行中获胜。如果游戏永远不会停止,则输出 Draw 一行。

在输出末尾打印换行符。


输入示例 1

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

输出示例 1

Sothe
  • 对于第一步,Cat Snuke 必须说出第一个词。
  • 对于第二步,如果 Wolf Sothe 说出了第 6 个词,Cat Snuke 将没有合适的词可用于下一步,因此 Wolf Sothe 获胜。

输入示例 2

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

输出示例 2

Draw

输入示例3

6 8
1 2
1 3
3 4
3 5
2 1
4 5
4 6
5 6

输出示例 3

Snuke

输入示例 4

4 8
2 3
2 3
3 4
4 1
3 1
2 2
4 2
4 3

输出示例 4

Sothe

请注意,对于第一步,可能没有合适的词可以说。