Fax McClad holding the dictionary of his new language.

Fax McClad, Croneria's most communicative bounty hunter, has recently created a secret language using English alphabet characters to be used by his crew members all across the Lylot system. He has a list of all possible words in this secret language, but would like to compress it before sending it to his crew.

To compress the data, Fax uses a tree data structure called a trie. Each node in the tree can have up to 26 children mapped using letters a to z. The tree initially consists of a root node. To add a new word, the following steps are performed:

1. Start at the root node (labelled 0)
2. Loop through each letter of the word in order
3. If the current node does not have a child that is mapped to that letter, add it
4. Move to the child mapped to that letter

For example, a trie containing only the words center, central, and centroid would only use 13 nodes, while sending all three words individually would require 21 letters.

However, Fax noticed that certain letters can be interchanged without much loss in meaning. For example, the letter u and v were considered the same letter in English for a very long time. To compress further, Fax chooses ~k,a~ and performs the following:

• Take each word with at least ~k~ letters. If the ~k^\text{th}~ letter is ~a~, replace it with a letter that is not ~a~. You may replace it with different letters for different words.

After doing this compression once, what is the number of nodes in the smallest trie he can make?

Constraints

For all testdata, ~N \le 2 \times 10^5~.

For testdata worth 50% of the points, ~N \le 5\,000~.

For testdata worth 30% of the points, ~N \le 500~.

For testdata worth 10% of the points, ~N \le 5~.

Input Specification

The first line will contain ~N~, the size of the trie.

The next ~N-1~ lines will describe the edges in the trie in the form a b c, indicating there is an edge from ~a~ to ~b~ mapped by the character c. Each edge is guaranteed to satisfy ~0 \le a < b < N~.

Output Specification

Output a single integer, the number of nodes in the smallest possible trie (including the root).

Sample Input 1

8
0 1 a
0 3 b
0 6 f
1 2 c
3 4 c
3 5 e
6 7 e

Sample Output 1

5

Explanation for Sample Output 1

Fax chooses ~k = 1~ and the letter b.

From the original trie, Fax extracts the words a b f ac bc be fe. He modifies this list of words to a a f ac ac fe fe respectively. The number of nodes in the new trie is ~5~, which is minimal.

Sample Input 2

11
0 1 c
1 2 e
2 3 n
3 4 t
4 5 r
5 6 a
5 8 o
6 7 l
8 9 i
9 10 d

Sample Output 2

10