题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXVIII Olimpiada Informatyczna – II etap Szablon Bajtogrodu

在 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 模板的数量。接下来的几行按字典序列出所有模板，每行一个。

13
1 2 A
1 3 A
2 4 B
3 5 B
4 6 A
4 7 A
5 8 A
5 9 A
6 10 B
7 11 B
8 12 B
13 9 B

14
AAB
AABAB
AB
ABAABAB
ABAB
BA
BAA
BAAB
BAABAB
BABA
BABAA
BABAAB
BABAABA
BABAABAB

提示

样例 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。

详细子任务附加限制及分值如下表所示。