AT_code_festival_2015_okinawa_d Dictionary for Shiritori Game

在一个国家里，使用着 $N$ 种不同的字符，并有一本包含 $M$ 个词条的字典，每个词条定义了一个单词。所有字符被编号为字符 $1$、字符 $2$、……、字符 $N$。字典中的第 $i$ 个词条（即一个单词）以字符 $p_i$ 开头，以字符 $q_i$ 结尾。 Snuke 猫和 Sothe 狼将用这本字典玩一种名为 **Shiritori** 的游戏（请注意，这里的 Shiritori 与通常的 Shiritori 游戏不同）。 - 首先由 Snuke 猫先手，然后两人轮流行动。 - 第一次行动时，当前玩家必须说出一个以字符 $1$ 开头的单词。如果没有任何以字符 $1$ 开头的单词可选，则当前玩家输掉游戏。 - 之后的每一步，当前玩家必须说出一个以上一步所说单词结尾字符为开头的单词。如果没有合适的单词可选，则当前玩家输掉游戏。 - **每个单词可以被重复使用任意次数**。 有些字典无论两位玩家如何努力都无法改变游戏结果。对于这些字典，请判断是先手玩家（Snuke 猫）获胜，还是后手玩家（Sothe 狼）获胜，或者游戏将永远不会结束。 所有的单词都已给出。假设两位玩家都会采取最优策略。请判断先手玩家（Snuke 猫）是否获胜，后手玩家（Sothe 狼）是否获胜，或游戏是否永远不会结束。

输入将通过标准输入给出，格式如下： > $N$ $M$ > $p_1$ $q_1$ > $p_2$ $q_2$ > ⋮ > $p_M$ $q_M$ - 第一行包含两个整数 $N$（$1 \leq N \leq 100\,000$）、$M$（$1 \leq M \leq 200\,000$）。 - 接下来的 $M$ 行，每行包含两个整数 $p_i$（$1 \leq p_i \leq N$）和 $q_i$（$1 \leq q_i \leq N$），表示一个单词以字符 $p_i$ 开头，以字符 $q_i$ 结尾。 可能存在不同的单词以相同的字符开头和结尾。换句话说，即使 $i \neq j$，也可能有 $p_i = p_j$ 且 $q_i = q_j$。

假设两位玩家都采取最优策略。如果先手玩家获胜，输出 `Snuke`；如果后手玩家获胜，输出 `Sothe`；如果游戏永远不会结束，输出 `Draw`。 输出需以换行符结尾。

### 题目说明 - 第一次行动时，Snuke 猫必须说出一个以字符 $1$ 开头的单词。如果没有合适的单词，则 Snuke 猫直接输掉游戏。 - 之后每一步，当前玩家必须说出一个以上一步单词结尾字符为开头的单词。如果没有合适的单词，则当前玩家输掉游戏。 - 每个单词可以被重复使用任意次数。 ### 样例解释 1 - 第一次行动时，Snuke 猫必须说出第一个单词。 - 第二步，如果 Sothe 狼说出了第 6 个单词，Snuke 猫将没有合适的单词可说，因此 Sothe 狼获胜。 ### 样例解释 4 请注意，第一次行动时可能没有合适的单词可说。 由 ChatGPT 4.1 翻译