给定大小为 $n$ 的字符集和 $m$ 个单词，第 $i$ 个单词以字符 $a_i$ 开头，以字符 $b_i$ 结尾。

Snuke 和 Sothe 轮流玩单词接龙游戏（Snuke 先手）。每次游戏那个人必须说出一个以上个单词的末尾字符开头的单词，第一个人必须说出一个以字符 1 开头的单词。若轮到该人进行游戏时，说不出符合条件的单词，则该人失败。

假设两人绝对聪明，判断谁是胜者或者游戏会永远进行下去。

$n\le 10^5,m\le 2\times 10^5$