Description

题目背景

公元2178年，人类在一颗遥远的行星上发现了外星生命。但是似乎这颗行星上只有单一物种而且它们并不像地球上的动物一样繁殖。更神奇的是，每个生物的基因构成是完全相同的！

每个生物的基因构成是单一核苷酸序列。在它们基因中有三种核苷酸，表示为‘A’ (腺嘌呤，Adenine), ‘C’ (胞嘧啶，Cytosine), and ‘M’ (膜嘌呤，Muamine)。根据某种假说，在这颗星球上只有某个新的核苷酸插入现存的生物基因序列某处时才会出现进化。如果这个改变是对进化有利的，这个带有新基因序列的生物会迅速取代没有变异的旧生物。

我们起初认为这种生物是从基因序列只含有单一核苷酸的生物经过多次上述的变异进化而来。然而化石证据表明可能并不是一直是这种情况。目前，与你协作的科研团队正在尝试证实“平行进化”的概念。“平行进化”指可能事实上有两条如同上述的进化路径，最终他们都进化成了这颗行星如今的物种。你的任务是证实平行进化假说是否与你的团队在化石中发现的遗传物质样本一致。

( TRANSLATED by @MolotovM)

题目含义

给定一个字符串和 $n$ 个字符串，求不多于两个的字符串的子串包含其他所有字符串，且这不多于两个的字符串都是给定字符串的子串。

Input Format

第一行输入为一个整数 $n (1\le n\le 4000)$，表示化石中发现的遗传物质样本数量

第二行输入为给定字符串表示当前生物的基因序列

接下来 $n$ 行，每行输入一个字符串，表示化石中发现的遗传物质样本

每个遗传物质样本由不超过 4000 个字母构成，且只包含大写字母A,C和M。

包括当前生物基因序列的所有基因序列都是独特的。

Output Format

输出每个化石中的遗传物质样本是怎样参与两条进化路径的。

第一行包含两个整数 $s_1,s_2$ 为两条进化路径的化石数量。

接下来 $s_1$ 行每行包含一个字符串表示第一条进化路径中的遗传物质样本

接下来 $s_2$ 行每行包含一个字符串表示第二条进化路径中的遗传物质样本

样本按年代顺序输出(从最早的开始)，如果一个样本可以同时出现在两条进化路径中，你需要表明它具体参与了哪种进化。

如果不可能满足有不多于两条进化路径，输出 "impossible"。

时空限制

时间限制: 2000 ms

空间限制: 1048576 kB

5
AACCMMAA
ACA
MM
ACMAA
AA
A

1 4
MM
A
AA
ACA
ACMAA

3
ACMA
ACM
ACA
AMA

impossible

1
AM
MA

impossible

4
AAAAAA
AA
AAA
A
AAAAA

0 4
A
AA
AAA
AAAAA