In Bajtogród, there are $n$ intersections connected by an economical network of two-way streets. The network is economical in the sense that there is exactly one way to travel from any intersection to any other. Each street has a name, as is typical in a city.

When Bajtek walks through the city, he writes down the first letters of the names of the streets he traverses. A walk along a sequence of consecutive streets (without turning back) is called a route. Thus, after traversing a specific route in the city, Bajtek writes down the string corresponding to that route.

Today, Bajtek walked along a certain route $T$ and noticed that it has a property that is as interesting as it is useless. Namely, if we consider all routes in Bajtogród that correspond to the same string as route $T$, they collectively traverse every street at least once. Bajtek says that the string corresponding to route $T$ is a Bajtogród template.

After a while, Bajtek began to wonder if he was certain that route $T$ is indeed a Bajtogród template. Or perhaps Bajtogród has no templates at all? Bajtek has asked you to investigate this issue and determine all Bajtogród templates, if any exist.

Input

The first line of the input contains a single integer $n$ ($2 \le n \le 2000$), representing the number of intersections in Bajtogród. We assume that the intersections are numbered from $1$ to $n$.

The next $n - 1$ lines describe the streets: the $i$-th line, for $i = 1, \dots, n - 1$, contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) representing the numbers of the intersections connected by the $i$-th street, and one uppercase English letter (A–Z) which is the first letter of that street's name.

Output

The first line of the output should contain a single integer representing the number of Bajtogród templates. The following lines should contain all the templates, one per line, in lexicographical order.

Examples

Input 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

Output 1

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

Note

The figure shows in red all six routes that correspond to the string AAB. Every street is traversed by at least one route, so AAB is one of the Bajtogród templates.

Test Cases

The test cases are categorized as follows:

• Test 1: $n = 21$; a path, street names alternate between A and B.
• Test 2: $n = 200$, no templates exist.
• Test 3: $n = 200$, a path, every street name starts with A.
• Test 4: $n = 1001$, a star graph consisting of five paths of length 200, every street name starts with A.
• Test 5: $n = 1001$, a star graph, street names start with A (half) and B (the other half).

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.