[IOI2008] Type Printer

题目描述

你需要利用一台可移动的打印机打印出$N$个单词。这种可移动式打印机是一种老式打印机，它需要你将一些小的金属块（每个包含一个字母）放到打印机上以组成单词。然后将这些小金属块压在一张纸上以打印出这个词。这种打印机允许你进行下列操作：

• 在打印机当前词的末端（尾部）添加一个字母；
• 在打印机当前词的尾部删去一个字母（将打印机当前词的最后一个字母删去）。仅当打印机当前至少有一个字母时才允许进行该操作；
• 将打印机上的当前词打印出来。 初始时打印机为空，或者说它不含任何带字母的金属块。打印结束时，允许有部分字母留在打印机内。同时也允许你按照任意的次序打印单词。

由于每一个操作都需要一定时间，所以需要你尽可能减少所需操作的总数目（将操作的总数最小化）。

你需要编写一个程序，给定所要打印的$N$个单词，找出以任意次序打印所有单词所需操作的最小数目，并输出一种这样的操作序列。

输入格式

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

输出格式

• 第一行包含一个整数$M$，表示打印这$N$个单词所需操作的最小数目。

• 接下来的$M$行，每行一个字符，表示你的操作序列，序列的描述方法如下：

  添加一个字母，用这个小写字母的自身来表示。

  删去一个字母，用-表示(减号，ASCII 45)。

  打印单词，用P表示(大写字母P)。

样例 #1

样例输入 #1

3
print
the
poem

样例输出 #1

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

提示

对于40分的数据，$n\leq18$。

对于所有数据，$1\leq N\leq25000$。