/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
天下一株式会社に勤務するワタナベくんは、社内のコミュニケーションにチャットツールを使っています。 チャットツールには補完機能があり、@で始まるアカウント名を入力しようとすると、プレフィックスの一致するアカウント名の一覧を辞書順で補完候補として表示してくれます。
ところが、ワタナベくんは補完候補の中から @yamamoto を選ぼうとした時に、間違って @yamada を選択してしまうことが多々あります。
@yamada は @yamamoto より辞書順で小さく、 @yama まで入力した際に、候補の先頭に表示されてしまうためです。
ワタナベくんは不思議な特技を持っていて、アルファベットの順番を自由に並べ替えることができます。
例えば、ワタナベくんが特技を使ってアルファベットの順番を abcefghijklmdnopqrstuvwxyz にすると、
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
1 yamamoto yamada
出力例 1
abcefghijklmdnopqrstuvwxyz
mdabcefghijklnopqrstuvwxyzやmabcefghijklnopqrstuvwxyzdも考えられるが、本来の辞書順で最も小さいabcefghijklmdnopqrstuvwxyzを出力する。
入力例 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より常に大きくなる。