配点 : 600 点
問題文
在 Tenkaichi Co., Ltd. 工作的渡边使用聊天工具进行内部沟通。 聊天工具具有补全功能,当您尝试输入以@开头的帐户名时,将按字典顺序显示具有匹配前缀的帐户名列表作为补全候选。
然而,当渡边试图从完成候选中选择@yamamoto时,他经常错误地选择@yamada。
按字典顺序,@yamada 比 @yamamoto 小。
这是因为,如果您输入最多 @yama ,它将显示在建议的开头。
渡边君拥有一种神秘的能力,可以让他自由地重新排列字母顺序。
例如,渡边君利用他的特殊技能改变了字母表的顺序。mdnopqrstuvwxyz
m 是
它仅由 d 较小,因此 @yamamoto 按字典顺序小于 @yamada 。
帐户名称 A_i 作为帐户名 B_i 要求按字典顺序缩小它。 给出了 N 。 找到渡边君的特殊技能重新排列的字母顺序,以满足所有给定的要求。 如果有多个字母顺序满足条件,则在排序前找到字母顺序的最小字典顺序。
制約
- 1 \leq N \leq 1000
- A_i \neq B_i
- 1 \leq |A_i|, |B_i| \leq 1000
- A_i,B_i由小写字母组成
入力
输入将以以下形式从标准输入给出。
N A_1 B_1 A_2 B_2 : A_N B_N
出力
满足条件的字母顺序中,输出最小的字典顺序一行。
如果不存在这样的字母顺序,则打印 -1。
入力例 1
1 yamamoto yamada
出力例 1
abcefghijklmdnopqrstuvwxyz
mdabcefghijklnopqrstuvwxyzmabcefghijklnopqrstuvwxyzd也是可能的,但 abcefghijkl 是原始词典顺序中最小的。md输出 nopqrstuvwxyz。
入力例 2
3 xx xy z w v w
出力例 2
abcdefghijklmnopqrstuvxyzw
入力例 3
2 a b b a
出力例 3
-1
没有满足条件的字母序列。
入力例 4
1 yamamoto yama
出力例 4
-1
yamamoto 总是比 yama 大。 求