CF2045H.Missing Separators

你有一个字典，其中的单词均已按照字母顺序排好，并且每个单词都是独特的，由大写英文字母构成。

现在你想打印这个字典，但不幸的是，打印系统出现了故障，所有单词都相连在一起打印，没有任何间隔符。因此，你得到一个字符串 $S$，它是字典中所有单词按顺序连接构成的。

你的任务是从字符串 $S$ 中将原来的字典单词分离出来。注意，分离出来的单词也必须是唯一的，并且按字母顺序排列。你需要尽可能多地复原字典中的单词数量。如果存在多个分离方案能够达到单词数量的最大值，你可以选择任意一种方案。

输入为一行，包含字符串 $S$（长度范围为 $1 \leq |S| \leq 5000$）。字符串 $S$ 只由大写字母组成。

首先输出一个整数，表示最多可以复原的单词数量，记作 $n$。

接下来输出 $n$ 行，每行表示一个单词。输出的单词需互不相同，并按字母顺序排列。按排列顺序连接这些单词后应完全等于输入字符串 $S$。

如果有多个方案可以实现最大单词数量，输出任意一种方案即可。

本翻译由 AI 自动生成