时间限制： 1.0 秒

空间限制： 256 MB

题目描述

小 H 想对一篇文章进行编码。

文章可以看做一个长为 $n$ 的全由小写字母构成的字符串，小 H 想用二进制来分别编码这些小写字母，将英文文本变成一个 $01$ 字符构成的文本。

比如对于文章 aaabbb，用 01 表示字母 a，用 10 表示字母 b，就会变成 010101101010。

不同的编码方式会让编码后的结果长度不一样，比如 aabbcc，如果用 00 表示 a，01 表示 b，10 表示 c，就会变成 000001011010。如果用 0 表示 a，用 10 表示 b，用 11 表示 c，则会变成 0010101111，长度会更短。

然而，并不是所有编码方案都能够解码。比如 aabbcc，如果使用 0 表示 a, 1 表示 b，10 表示 c 的话，编码会得到 00111010。可是，当我们遇到了 10 时，就无法知道对应的是 c 还是 ba 了。

因此，我们定义一种合法的编码方式为：任意一个字符对应的编码，不能是另一个字符对应编码的前缀。

现在，小 H 给了你这篇文章，请你输出任意一种最优编码方式，并输出使用该编码方式后文章的长度。

输入格式

从标准输入读入数据。

仅一行，内容为一个长为 $n$ 的全小写字符串。

输出格式

输出到标准输出。

第一行一个整数，表示最优编码下的编码后长度。

接下来有若干行，每行开头一个小写字母，接着跟一个空格，再然后跟一个长度不超过 $100$ 的 $01$ 字符串（最优情况下编码长度肯定不超过 $100$），表示将该小写字母编码成什么样的 $01$ 字符串。

我们首先会检查你最优编码长度计算是否正确，接着会检查你的编码方式是否合法，以及使用你的编码方式是否能达到最优编码长度。

对于在原字符串中未出现过的字符，你可以不输出，也可以随便输一个不超过 $100$ 的 $01$ 字符串。对于原字符串中出现过的字符，你必须输出他的编码方案。

aabc

6
a 1
b 00
c 01

子任务

对于所有数据，保证 $1\le n\le 5\times 10^5$。

提示

Chap 05，二叉树，最优 PFC 编码

前缀无歧义编码（prefix-free code，简称 PFC）是一种对字符的编码方案。在只有 $01$ 串的情况下，任意一种 PFC 方案本质上对应一种真二叉树的结构。Huffman 编码则是最优 PFC 编码方案。

本题当中，我们并不要求 Huffman 最优编码的时间复杂度，但是你需要输出任意一种具体的 PFC 编码方案。

边界情况：如果全篇文章只有 1 种字符呢？

来源

DSA OJ 编程作业