Unique Username

题目描述

Takahashi 在决定某个服务的用户名时遇到了困难。请写一段代码来帮助他。

找到一个字符串 $X$，满足下列所有条件：

$X$ 是通过下列过程得到的： 令 $S_1', S_2', \ldots,S_N'$ 为 $S_1, S_2, \ldots,S_N$ 的一个排列。$X$ 为按此顺序连接 $S_1'$、（$1$ 个或更多的 _ 的拷贝）、$S_2'$、（$1$ 个或更多的 _ 的拷贝）、$\ldots$、（$1$ 个或更多的 _ 的拷贝）、和 $S_N'$ 的结果。

$X$ 的长度在 $3$ 到 $16$（含）之间。 $X$ 不与任意 $M$ 个字符串 $T_1,T_2,\ldots,T_M$ 中的任何一个相同。

如果不存在满足所有条件的 $X$，则输出 $-1$。

输入格式

输入按下列格式从标准输入给出： $N$ $M$ $S_1$ $S_2$ $\vdots$ $S_N$ $T_1$ $T_2$ $\vdots$ $T_M$

输出格式

输出一个满足所有条件的字符串 $X$。如果不存在满足条件的 $X$，则输出 $-1$。
如果存在多个解，输出任意一个。

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$。 $S_i$ 是由小写英文字母组成的字符串。 $3 \leq |T_i| \leq 16$ 如果 $i \neq j$，则 $T_i \neq T_j$。 $T_i$ 是由小写英文字母和 _ 组成的字符串。满足第一和第二条条件的唯一字符串是 $X=$ $chokudai$，但它与 $T_1$ 相同。
因此，不存在满足所有条件的 $X$，应该输出 $-1$。
像 choku__dai（在 $choku$ 和 $dai$ 之间有两个 _）这样的字符串也满足所有条件。
chokudai__atcoder 和 atcoder__chokudai（在 $chokudai$ 和 $atcoder$ 之间有两个 _）的长度为 $17$，这违反了第二条条件。
给定的 $T_i$ 中可能包含不能通过第一条所述过程得到的字符串。

标签: AtCoder|abc268D

来源

AtCoder|abc268D