← 返回题目列表

AtCoder · tenka1_2016_qualA_c

C. 山田山本问题

中文机器翻译题面 查看原题

配点 : 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 大。 求