# dyy记单词 ## 题目背景 dyy是班里的记单词高手，请你帮他记单词。 ## 题目描述 dyy记单词的方式很特别，他会记住这个单词由哪几个字母组成，在记住 $n$ 组 $(a,b)$ ,表示字母 $a$ 是字母 $b$ 的前一个，请判断能否记住这个单词。 ## 输入格式 输入共 $n+2$ 行。第一行有两个整数 $m,n$， $m$ 表示这个单词有多少个字母， $n$ 如题所示。 第二行有 $m$ 个字符组成的字符串 $s$ ，表示单词有哪些字符，顺序随机。 接下来 $n$ 行每行两个字符 $a,b$，含义如题所示，保证 $s$ 包含 $a$ 和 $b$。 ## 输出格式 输出只有一行。如果可以确定该单词的唯一可能，那么输出该单词，否则，输出`-1`。 ## 样例 #1 ### 样例输入 #1 ``` 2 1 ca a c ``` ### 样例输出 #1 ``` ac ``` ## 样例 #2 ### 样例输入 #2 ``` 3 1 cab b c ``` ### 样例输出 #2 ``` -1 ``` ## 提示 $2 < m < 10^2或m=0,0 < n < 10或n=0$\ 保证s中不出现重复字符 请给出标准代码

以下是Python3的标准代码实现：

m, n = map(int, input().split())
s = input().strip()
pre = {s[i]: s[i] for i in range(m)}
for i in range(n):
    a, b = input().split()
    pre[b] = a

# 找到每个字符的最终前驱
for i in range(26):
    for j in range(26):
        if pre.get(chr(ord('a')+i)) == pre.get(chr(ord('a')+j)):
            pre[chr(ord('a')+j)] = pre[chr(ord('a')+i)]

# 判断是否存在前驱相同的字符
for i in range(m-1):
    if pre[s[i]] != pre[s[i+1]]:
        print(-1)
        break
else:
    print(''.join([pre[s[i]] for i in range(m)]))

具体思路如下：

首先读入单词中的字符和每个字符的前驱，用一个字典记录下来。然后，我们需要找到每个字符的最终前驱，即如果 $a$ 是 $b$ 的前驱，$b$ 是 $c$ 的前驱，那么 $c$ 的最终前驱应该是 $a$。

接下来，我们判断单词中是否存在前驱相同的字符，如果有，说明不能确定唯一可能，输出 -1；否则，将每个字符的最终前驱拼接起来即为单词的唯一可能。

注意，这里我们用了一个小技巧，即在字典初始化时，将每个字符的前驱初始化为它本身，这样在找每个字符的最终前驱时就不需要判断是否存在没有前驱的字符了。