P14648 [POI 2025/2026 #1] 浏览器 / Przeglądarka internetowa

Bajtosia 正在为信息学课程准备一个演示文稿。为此，她必须访问 $n$ 个具有两两不同地址的网站，从中获取所需的信息。 Bajtosia 使用的浏览器有一个文本框，初始时包含空串。通过按键可以修改文本框中的内容，并访问地址等于当前文本框中单词的网站。可用的操作如下： 1. 按键 $\texttt{a}$ 到 $\texttt{z}$ 会在当前单词的末尾追加按下的字母。 2. 按键 $\texttt{BACKSPACE}$ 删除当前单词的最后一个字母（如果当前单词为空串则什么也不做）。 3. 按键 $\texttt{ENTER}$ 会访问地址等于当前单词的网站，然后清空文本框中的单词（即将其变为空串）。 4. 按键 $\texttt{TAB}$ 会将当前单词自动补全为在所有已经访问过的、以当前单词为前缀（即开头片段）的页面中最近一次访问的那一个页面的地址（如果不存在这样的已访问页面，则什么也不做）。 离提交演示文稿的截止时间已经不多了，因此 Bajtosia 想以尽可能少的按键次数访问所有要求访问的网站。Bajtosia **不能**访问除要求访问的网站以外的其他网站。Bajtosia 可以以**任意**顺序访问这些要求访问的网站，并且每个网站必须被访问**恰好一次**。 请帮助 Bajtosia，求出所需的最小按键次数，以及应该依次按下哪些按键。

输入的第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示 Bajtosia 需要访问的网站数量。 在接下来的第 $i$ 行（对于 $1 \le i \le n$）中，给出一个非空字符串 $s_i$，由英文小写字母（$\texttt{a}\sim \texttt{z}$）组成，表示第 $i$ 个网站的地址。字符串 $s_i$ 两两不同。 记 $S = |s_1| + \dots + |s_n|$，则有 $S \le 10^6$。

输出的第一行应输出一个整数 $k$，表示访问所有给定网站所需的最小按键次数。 输出的第二行应包含一个长度为 $k$ 的按键序列，即为依次按下的按键，从而能够访问所有给定的网站。按键 `BACKSPACE`、`ENTER` 和 `TAB` 分别用字母 `B`、`E` 和 `T` 来表示。 如果存在多个可行解，可以输出其中任意一个。

### 样例解释 一开始，Bajtosia 逐个字母地在文本框中输入字符串 $\texttt{aaaaba}$，然后按下 $\texttt{ENTER}$。接着她按下 $\texttt{TAB}$，此时文本框中又出现了字符串 $\texttt{aaaaba}$。然后 Bajtosia 连续两次按下 $\texttt{BACKSPACE}$，得到 $\texttt{aaaa}$，再追加两个字母，得到 $\texttt{aaaadb}$，之后按下 $\texttt{ENTER}$。接下来，她按下 $\texttt{TAB}$，再按两次 $\texttt{BACKSPACE}$，再次得到 $\texttt{aaaa}$。最后 Bajtosia 再输入四个字母得到 $\texttt{aaaaczzz}$，并最后一次按下 $\texttt{ENTER}$。 整个过程也在“样例图解”一节的示意图中给出。 ### 大样例 可以在附件中获得大样例。 样例 $\texttt{0a}$ 是题面中展示的样例。此外： * $\texttt{0b}$：$n = 26$ 个字符串，每个由 $20\,000$ 个字符组成。每个字符串的前 $19\,999$ 个字符都是字母 `a`，而它们的最后一个字符依次为英文小写字母 `a`、`b`、...、`z`。 * $\texttt{0c}$：$n = 10$ 个字符串，第 $i$ 个字符串（对于 $i = 1, \dots, 10$）由字母 `'a'` 重复 $18i$ 次组成。 * $\texttt{0d}$：$n = 65534$ 个字符串。输入中包含所有由字母 `'a'` 和 `'b'` 组成、长度不超过 $15$ 的非空字符串。 * $\texttt{0e}$：$n = 2$ 个字符串。两个字符串的长度都是 $500\,000$，并且在前 $300\,000$ 个位置上的字母完全相同。在第 $300\,001$ 个位置上的字符二者不同。之后的字符是随机的。 ### 子任务 本题采用捆绑测试。 | 子任务编号 | 限制 | 得分 | | :---------: | :--------------------- | :-----: | | 1 | $n \le 8$ 且对所有 $i \in [1..n]$ 均有 $\vert s_i\vert \le 10$ | 17 | | 2 | 所有 $s_i$ 的长度相同 | 12 | | 3 | $S \le 1\,000$ | 32 | | 4 | $s_i$ 只由字母 `a` 和 `b` 构成 | 18 | | 5 | 无额外限制 | 21 | 如果你的输出中只有第一行是正确的，你的解法在该测试上将得到该测试分值的 $80\%$。你不必输出第二行也能获得这些分数。 ### 样例图解 在下面的示意图中，给出了上文所述示例测试的一种解法的各个步骤。 ::::align{center}  ::::