题目描述

题目译自 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

样例 2

见附加文件下 [sza1.in](file:sza1.in) 和 [sza1.out](file:sza1.out)。

该样例满足 $n=21$，路径为一条直线，街道名称首字母交替为 A 和 B；

样例 3

见附加文件下 [sza2.in](file:sza2.in) 和 [sza2.out](file:sza2.out)。

该样例满足 $n=200$，没有模板；

样例 4

见附加文件下 [sza3.in](file:sza3.in) 和 [sza3.out](file:sza3.out)。

该样例满足 $n=200$，路径为一条直线，每条街道名称首字母均为 A；

样例 5

见附加文件下 [sza4.in](file:sza4.in) 和 [sza4.out](file:sza4.out)。

该样例满足 $n=1001$，星形结构，由五条长度为 $200$ 的路径组成，每条街道名称首字母均为 A；

样例 6

见附加文件下 [sza5.in](file:sza5.in) 和 [sza5.out](file:sza5.out)。

该样例满足 $n=1001$，星形结构，街道名称首字母一半为 A，一半为 B。

数据范围与提示

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

子任务	附加限制	分值
$1$	$n \leq 50$	$15$
$2$	$n \leq 200$	$35$
$3$	无附加限制	$50$