原题链接

D - Unique Username

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

高桥君有取名选择困难症，于是他找到你，希望帮他取一个用户名。

具体取名规则是：把给定的 $N$ 个字符串 $S_1，S_2,\ldots,S_N$ 以任意顺序排列，并在每两个字符串中间加 $\ge1$ 个下划线，要求不能与后面给定的 $M$ 个字符串 $T_1，T_2,\ldots,T_M$ 中的任意一个相同。

其中，你给出的字符串的长度 $X$ 应该满足 $3\le X \le 16$ 。如果无法满足条件，输出 $-1$。

输入格式

第一行两个整数，分别为 $N$ 和 $M$ ；

后 $N$ 行每行一个字符串 $S_i$ ；

后 $M$ 行每行一个字符串 $T_i$ 。

1 1
chokudai
chokudai

-1

2 2
choku
dai
chokudai
choku_dai

dai_choku

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

-1

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

ab__ef___cd_gh

提示

• $1\ \leq\ N\ \leq\ 8$
• $0\ \leq\ M\ \leq\ 10^5$
• $N,M$ は整数
• $1\ \leq\ |S_i|\ \leq\ 16$
• $N-1+\sum{|S_i|}\ \leq\ 16$
• 当 $i\ \neq\ j$ 且 $S_i\ \neq\ S_j$
• $3\ \leq\ |T_i|\ \leq\ 16$
• 当 $i\ \neq\ j$ 且 $T_i\ \neq\ T_j$
• $T_i$ 都是小写英文字母构成。