P12915 [POI 2020/2021 R2] 模板 / Szablon Bajtogrodu

翻译来自于 [LibreOJ](https://loj.ac/p/4833)。

**题目译自 [XXVIII Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi28-2/dashboard/) [Szablon Bajtogrodu](https://szkopul.edu.pl/problemset/problem/y-mTVYClxMJcgMhUnHaUqPPq/statement/)** 在 Bajtogród 里有 $n$ 个路口，它们通过一个简洁的双向街道网络连接在一起。这个网络之所以简洁，是因为从任意一个路口到另一个路口，恰好只有一条路径。每条街道都有自己的名字，就像城市里常见的那样。 当 Bajtek 在城里散步时，他会记下经过的每条街道名称的首字母。沿着若干连续街道（不回头）走过的路线，我们称之为一条**路径**。于是，走完某条路径后，Bajtek 会记下一个与这条路径对应的字符串。 今天，Bajtek 走了一条路径 $T$，发现它有个既有趣又没啥实际用处的特性：如果在 Bajtogród 中找出所有与路径 $T$ 对应相同字符串的路径，这些路径加起来至少会经过每条街道一次。Bajtek 把这种路径对应的字符串称为 **Bajtogród 的模板**。 过了一会儿，Bajtek 开始怀疑，自己认定的路径 $T$ 是否真的是 Bajtogród 的模板？或者，Bajtogród 根本就没有模板？他请你帮忙研究这个问题，找出 Bajtogród 所有的模板（如果存在的话）。

输入的第一行包含一个整数 $n$ $(2 \leq n \leq 2000)$，表示 Bajtogród 中路口的数量。我们假设路口编号从 $1$ 到 $n$。 接下来的 $n-1$ 行描述街道：第 $i$ $(1\leq i\leq n-1)$ 行包含两个整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i}, b_{i} \leq n, a_{i} \neq b_{i})$，表示第 $i$ 条街道连接的两个路口编号，以及一个大写英文字母，表示这条街道名称的首字母。

输出的第一行应包含一个整数，表示 Bajtogród 模板的数量。接下来的几行按字典序列出所有模板，每行一个。

**样例 1 解释**  在这个例子中，所有对应字符串 `AAB` 的六条路径（图中标红）加起来覆盖了每条街道至少一次，因此 `AAB` 是字节城的模板之一。 **附加样例** 1. 该样例满足 $n=21$，路径为一条直线，街道名称首字母交替为 `A` 和 `B`； 2. 该样例满足 $n=200$，没有模板； 3. 该样例满足 $n=200$，路径为一条直线，每条街道名称首字母均为 `A`； 4. 该样例满足 $n=1001$，星形结构，由五条长度为 $200$ 的路径组成，每条街道名称首字母均为 `A`； 5. 该样例满足 $n=1001$，星形结构，街道名称首字母一半为 `A`，一半为 `B`。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 50$ | $15$ | | $2$ | $n \leq 200$ | $35$ | | $3$ | 无附加限制 | $50$ |