102683: [AtCoder]ABC268 D - Unique Username

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

Takahashi is having trouble with deciding a username for a service. Write a code to help him.

Find a string $X$ that satisfies all of the following conditions:

  • $X$ is obtained by the following procedure:
    • Let $S_1', S_2', \ldots,S_N'$ be a permutation of $S_1, S_2, \ldots,S_N$. Let $X$ be the concatenation of $S_1'$, ($1$ or more copies of _), $S_2'$, ($1$ or more copies of _), $\ldots$, ($1$ or more copies of _), and $S_N'$, in this order.
  • The length of $X$ is between $3$ and $16$, inclusive.
  • $X$ does not coincide with any of $M$ strings $T_1,T_2,\ldots,T_M$.

If there is no $X$ that satisfies all of the conditions, print -1 instead.

Constraints

  • $1 \leq N \leq 8$
  • $0 \leq M \leq 10^5$
  • $N$ and $M$ are integers.
  • $1 \leq |S_i| \leq 16$
  • $N-1+\sum{|S_i|} \leq 16$
  • $S_i \neq S_j$ if $i \neq j$.
  • $S_i$ is a string consisting of lowercase English letters.
  • $3 \leq |T_i| \leq 16$
  • $T_i \neq T_j$ if $i \neq j$.
  • $T_i$ is a string consisting of lowercase English letters and _.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$
$T_1$
$T_2$
$\vdots$
$T_M$

Output

Print a string $X$ that satisfies all of the conditions. If there is no $X$ that satisfies all of the conditions, print -1 instead.
If there are multiple solutions, print any of them.


Sample Input 1

1 1
chokudai
chokudai

Sample Output 1

-1

The only string that satisfies the first and second conditions is $X=$ chokudai, but it coincides with $T_1$.
Thus, there is no $X$ that satisfies all of the conditions, so -1 should be printed.


Sample Input 2

2 2
choku
dai
chokudai
choku_dai

Sample Output 2

dai_choku

Strings like choku__dai (which has two _'s between choku and dai) also satisfy all of the conditions.


Sample Input 3

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

Sample Output 3

-1

chokudai__atcoder and atcoder__chokudai (which have two _'s between chokudai and atcoder) have a length of $17$, which violates the second condition.


Sample Input 4

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

Sample Output 4

ab__ef___cd_gh

The given $T_i$ may contain a string that cannot be obtained by the procedure described in the first condition.

Input

题意翻译

高桥君有取名选择困难症,于是他找到你,希望帮他取一个用户名。 具体取名规则是:把给定的 $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$ 。 输出格式 一个满足题意的字符串 $X$ 。如果没有满足的,输出一个数 $-1$ 。

Output

分数:400分

问题描述

高桥凉介正在为一个服务决定用户名,但遇到了困难。编写一个代码来帮助他。

找到一个满足以下所有条件的字符串$X$:

  • $X$是通过以下过程获得的:
    • 将$S_1, S_2, \ldots,S_N$排列为$S_1', S_2', \ldots,S_N'$。将$S_1'$,(1个或多个_),$S_2'$,(1个或多个_),$\ldots$,(1个或多个_),和$S_N'$按此顺序连接起来。
  • $X$的长度在3到16之间(含3和16)。
  • $X$不与任何字符串$T_1,T_2,\ldots,T_M$相等。

如果没有满足所有条件的$X$,则打印-1

约束条件

  • $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$。
  • $S_i$是一个由小写英文字母组成的字符串。
  • $3 \leq |T_i| \leq 16$
  • 如果$i \neq j$,则$T_i \neq T_j$。
  • $T_i$是一个由小写英文字母和_组成的字符串。

输入

输入通过标准输入给出,格式如下:

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$
$T_1$
$T_2$
$\vdots$
$T_M$

输出

打印一个满足所有条件的字符串$X$。如果没有满足所有条件的$X$,则打印-1
如果有多个解,打印其中任何一个即可。


样例输入1

1 1
chokudai
chokudai

样例输出1

-1

满足第一和第二个条件的唯一字符串是$X=$ chokudai,但它与$T_1$相等。
因此,没有满足所有条件的$X$,因此应该打印-1


样例输入2

2 2
choku
dai
chokudai
choku_dai

样例输出2

dai_choku

choku__dai(在chokudai之间有两个_)这样的字符串也满足所有条件。


样例输入3

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

样例输出3

-1

chokudai__atcoderatcoder__chokudai(在chokudaiatcoder之间有两个_)的长度为17,违反了第二个条件。


样例输入4

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

样例输出4

ab__ef___cd_gh

给定的$T_i$可能包含一个不能通过第一个条件中描述的过程获得的字符串。

加入题单

上一题 下一题 算法标签: