[IOI2008] Type Printer

题目描述

你需要利用一台可移动的打印机打印出 $n$ 个单词。这种可移动式打印机是一种老式打印机,它需要你将一些小的金属块(每个包含一个字母)放到打印机上以组成单词。然后将这些小金属块压在一张纸上以打印出这个词。这种打印机允许你进行下列操作: - 在打印机当前词的末端(尾部)添加一个字母; - 在打印机当前词的尾部删去一个字母(将打印机当前词的最后一个字母删去)。仅当打印机当前至少有一个字母时才允许进行该操作; - 将打印机上的当前词打印出来。 初始时打印机为空,或者说它不含任何带字母的金属块。打印结束时,允许有部分字母留在打印机内。同时也允许你按照任意的次序打印单词。 由于每一个操作都需要一定时间,所以需要你尽可能减少所需操作的总数目(将操作的总数最小化)。 你需要编写一个程序,给定所要打印的 $n$ 个单词,找出以任意次序打印所有单词所需操作的最小数目,并输出一种这样的操作序列。

输入输出格式

输入格式


- 第 $1$ 行包含一个整数 $n$, 表示你需要打印的单词数。 - 随后的 $n$ 行中,每一行都包含一个单词。每个词仅由小写字母组成,而且单词的长度为 $1$ 到 $20$ 个字母(包含 $1$ 和 $20$ 在内)。所有单词都不相同。

输出格式


第一行包含一个整数 $m$,表示打印这 $n$ 个单词所需操作的最小数目。 接下来的 $m$ 行,每行一个字符,表示你的操作序列,序列的描述方法如下: - 添加一个字母,用这个小写字母的自身来表示。 - 删去一个字母,用 `-` 表示。 - 打印单词,用 `P` 表示。

输入输出样例

输入样例 #1

3
print
the
poem

输出样例 #1

20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

说明

对于 $40\%$ 的数据,$n\leq18$; 对于 $100\%$ 的数据,$1\leq n\leq25000$。