出题人 01 买了一只同构判定鸭。一买回来，这只鸭就嘎嘎地叫着：“我是同构判定鸡的同类，可以判定两张图是否一样！”

具体来说，同构判定鸭的工作逻辑如下:

• 给定同构判定鸭两张有向图 $G_1,G_2$，每条边上都写有小写字母。
• 对于图上的一条路径和一个非空字符串 $S$，我们称这条路径和 $S$ 匹配当且仅当按照顺序写下路径上所有边的字母所得到的字符串恰好等于 $S$。
• 定义一个非空字符串 $S$ 在图 $G$ 上的出现次数为 $G$ 中与 $S$ 匹配的不同路径条数。
• 定义一个非空字符串 $S$ 是好串，当且仅当其在 $G_1$ 中出现次数和 $G_2$ 中出现次数相等。否则我们称之为坏串。
• 同构判定鸭判定两张图 $G_1$,$G_2$ 等价当且仅当所有非空小写字符串 $S$ 都是好串。

但是作为一名有经验的出题人，出题人 01 并不能轻易相信同构判定鸭的结果。

因此他找到你，让你帮他判断两张图是否等价。若不相同，你需要给出长度最短的坏串。若有多个长度最短的坏串，你需要给出其中字典序最小的。

注意本题并不讨论空串的情况。空串不是好串也不是坏串。

输入格式

输入的两部分分别描述 $G_1,G_2$，对于一张图：

第一行两个正整数 $n,m$，表示图的点数和边数。

接下来 $m$ 行，每行两个正整数 $x_i,y_i$ 和一个小写字母 $c_i$，表示一条从 $x_i$ 出发，到 $y_i$ 结束的有向边，边上的字母为 $c_i$。

两张图之间没有额外的空行做分隔。

输出格式

若两张图等价，则输出 "Same"。

否则按照题目要求输出最短的坏串中字典序最小的。

注意，如果答案是"Same"而你输出了"same"，你的输出将会被判定为错误。

样例一

input

3 3
1 2 a
2 3 b
3 1 c
3 3
1 2 b
2 3 c
3 1 a

output

Same

explanation

将 $G_2$ 中的点按照 $1\to 2,2\to 3,3\to 1$ 重标号后，不难发现其与 $G_1$ 完全相同，自然每个非空小写字符串 $S$ 在两图中的出现次数都相等了。

样例二

input

6 6
1 3 a
1 4 a
2 4 b
3 5 a
3 6 b
4 6 b
6 6
1 3 a
1 4 a
2 4 b
3 5 a
4 5 b
4 6 b

output

bb

样例三

见样例数据下载。

该样例范围同测试包 2。

样例四

见样例数据下载。

该样例范围同测试包 2。

数据范围

对于所有测试数据，满足 $1\le n\le 500,0\le m\le 3000$。

保证图中不存在自环，但是可能会存在重边。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载