题目描述

It is 2178, and alien life has been discovered on a distant planet. There seems to be only one species on the planet and they do not reproduce as animals on Earth do. Even more amazing, the genetic makeup of every single organism is identical!

The genetic makeup of each organism is a single sequence of nucleotides. The nucleotides come in three types, denoted by ‘A’ (Adenine), ‘C’ (Cytosine), and ‘M’ (Muamine). According to one hypothesis, evolution on this planet occurs when a new nucleotide is inserted somewhere into the genetic sequence of an existing organism. If this change is evolutionarily advantageous, then organisms with the new sequence quickly replace ones with the old sequence.

It was originally thought that the current species evolved this way from a single, very simple organism with a single-nucleotide genetic sequence, by way of mutations as described above. However, fossil evidence suggests that this might not have been the case. Right now, the research team you are working with is trying to validate the concept of “parallel evolution” – that there might actually have been two evolutionary paths evolving in the fashion described above, and eventually both paths evolved to the single species present on the planet today. Your task is to verify whether the parallel evolution hypothesis is consistent with the genetic material found in the fossil samples gathered by your team.

输入格式

The input begins with a number $n$ ($1\le n\le 4\, 000$) denoting the number of nucleotide sequences found in the fossils. The second line describes the nucleotide sequence of the species currently living on the planet. Each of the next $n$ lines describes one nucleotide sequence found in the fossils.

Each nucleotide sequence consists of a string of at least one but no more than $4\, 000$ letters. The strings contain only upper-case letters A, C, and M. All the nucleotide sequences, including that of the currently live species, are distinct.

输出格式

Display an example of how the nucleotide sequences in the fossil record participate in two evolutionary paths. The example should begin with one line containing two integers $s_1$ and $s_2$, the number of nucleotide sequences in the fossil record that participate in the first path and second path, respectively. This should be followed by $s_1$ lines containing the sequences attributed to the first path, in chronological order (from the earliest), and then $s_2$ lines containing the sequences attributed to the second path, also in chronological order. If there are multiple examples, display any one of them. If it is possible that a sequence could appear in the genetic history of both species, your example should assign it to exactly one of the evolutionary paths.

If it is impossible for all the fossil material to come from two evolutionary paths, display the word impossible.

题目大意

题目背景

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

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

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

( TRANSLATED by @MolotovM)

题目含义

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

输入格式

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

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

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

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

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

输出格式

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

第一行包含两个整数$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

提示

Time limit: 2000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2015