在 Bajtogród 市，有 $n$ 个路口，它们由一个经济的街道网络连接。该网络是“经济的”，意味着从任意一个路口到另一个路口都有且仅有一条路径。每条街道都有一个名字。

当 Bajtek 在城市中行走时，他会记录下他所经过的街道名称的首字母。我们将沿着若干条连续街道的行走（不掉头）称为一条“路线”。因此，在走完一条特定的路线后，Bajtek 会记录下对应于该路线的字符串。

今天，Bajtek 走了一条路线 $T$，并注意到它具有一个既有趣又无用的特性：如果我们考虑 Bajtogród 中所有对应字符串与路线 $T$ 相同的路线，那么这些路线的总和覆盖了每一条街道至少一次。Bajtek 称对应于路线 $T$ 的字符串为 Bajtogród 的“模板”。

片刻之后，Bajtek 开始怀疑他是否弄错了路线 $T$ 是否真的是 Bajtogród 的模板。或者，也许 Bajtogród 根本没有模板？Bajtek 请你研究这个问题，并找出 Bajtogród 的所有模板（如果存在的话）。

输入格式

输入的第一行包含一个整数 $n$ ($2 \le n \le 2000$)，表示 Bajtogród 的路口数量。假设路口编号为 $1$ 到 $n$。

接下来的 $n-1$ 行描述了街道：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示第 $i$ 条街道连接的路口编号，以及一个大写英文字母（A–Z），表示该街道名称的首字母。

输出格式

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

样例

输入 1

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

输出 1

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

说明

图中红色标记了所有对应字符串为 AAB 的六条路线。每一条街道至少被一条路线经过，因此 AAB 是 Bajtogród 的模板之一。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。