No.517 壊れたアクセサリー

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 77
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : ixmelixmel

0 ProblemId : 1007 / 出題時の順位表

問題文

注意!:ストーリーを読むよりサンプル1、2、3を読んだほうが早いですよ。

結城君と幸田さんは文字列を使ったアクセサリーを作った。
アクセサリーはアルファベットが1文字描かれた石をいくつか紐で1列に繋いだものである。
アルファベットは大文字で1つのアクセサリーに同じアルファベットは2つ無い。
石を紐で繋ぐと先頭から終端に向けて文字列を読むことができる。
結城君と幸田さんは同じ文字列のアクセサリーを2つ作ってそれぞれ1つずつ持ち帰った。

10年後。
結城君と幸田さんはお互いのアクセサリーを持ち寄った。
しかし、2つのアクセサリーは紐の強度が弱く何箇所か切れていた。
(テストケースにはまったく切れていなかった場合もあります。)
結城君と幸田さんはもともとどんな文字列が描いてあったのか全く忘れてしまった。
幸い全ての石は紛失せずにすべて残っている。
結城君と幸田さんはお互いの壊れたアクセサリーを手掛かりに元の文字列を思い出せるだろうか?
思い出せる場合はその文字列を答えよ。
不可能な場合には-1を答えとせよ。

入力

$N$
$A_0$
$A_1$
$\vdots$
$A_{N-1}$
$M$
$B_0$
$B_1$
$\vdots$
$B_{M-1}$

Nは結城君のアクセサリーの断片の個数。$1\le N \le 26$。
$A_i$は結城君のi番目のアクセサリーの断片から読み取れる文字列。
Mは幸田さんのアクセサリーの断片の個数。$1\le M \le 26$。
$B_i$は幸田さんのi番目のアクセサリーの断片から読み取れる文字列。
文字列の左から右の向きがアクセサリーの先頭から終端の向きに対応する。
文字列に含まれる文字はすべて大文字のアルファベットである。
1つのアクセサリーに同じ文字が2つ以上含まれない。
結城君のアクセサリーに含まれるアルファベットが幸田さんのアクセサリーにも必ず含まれる。

出力

もともとアクセサリーに描いてあった文字列が1つに確定できれば1行で出力せよ。
確定できずわからない場合は-1を1行で出力せよ。
最後に改行を忘れずに。

サンプル

サンプル1
入力
2
YUKI
CODER
3
YU
KICO
DER
出力
YUKICODER

結城君は石が「Y-U-K-I」と「C-O-D-E-R」の2つの繋がった断片を持っています。
幸田さんは「Y-U」と「K-I-C-O」と「D-E-R」の3つの繋がった断片を持っています。
まず幸田さんの情報から「I」と「C」の順で繋がっていることがわかります。
また、結城さんの「Y-U-K-I」と「C-O-D-E-R」はもともとこの順で繋がっていたことがわかります。
よって、アルファベットの異なるアクセサリーの文字列は「Y-U-K-I-C-O-D-E-R」と確定できます。

サンプル2
入力
2
EA
T
2
T
EA
出力
-1

文字列は「EAT」かもしれませんし「TEA」かもしれません。
2通りの可能性があるのでもともとどんな文字列だったのかはわかりません。

サンプル3
入力
1
X
1
X
出力
X

アクセサリーは「X」の1文字だけだったので答えも「X」です。

サンプル4
入力
4
MA
V
PWXHQ
ID
5
H
A
QVM
I
DPWX
出力
IDPWXHQVMA

提出ページヘ