Ta định nghĩa một cây Trie như sau:

• Cây có gốc.

• Mỗi đỉnh ~i~ của cây thể hiện một xâu kí tự, ký hiệu là ~S_i~.

• Mỗi cạnh của Trie được gán một kí tự ~c~.

• Xâu ký tự ứng với đỉnh gốc là xâu rỗng.

• Với mỗi cạnh ~u, v~ được gán ký tự ~c~, trong đó u là đỉnh gần gốc hơn (u là cha của v), ~S_v = S_u + c~.

Cây Trie được gọi là hoàn hảo nếu như tất cả các giá trị ~S_i~ đôi một phân biệt.

Cho một cây ~T~ có ~n~ đỉnh, các cạnh được gán sẵn kí tự. Hãy đếm số đỉnh ~u~ sao cho ~T~ là một cây Trie hoàn hảo nếu chọn ~u~ làm gốc của ~T~.

Input

Vào từ file văn bản trie.inp:

Dòng đầu gồm một số nguyên dương ~n~ là số đỉnh trong cây ~(1 \le n \le 10^5)~.

~n - 1~ dòng tiếp theo, mỗi dòng có dạng ~u~ ~v~ ~c~ thể hiện một cạnh nối từ đỉnh ~u~ đến đỉnh ~v~ và được gán ký tự ~c~ ~(1\le u, v \le n, u \ne v, c~ là chữ cái tiếng Anh viết thường~)~.

Output

In ra file văn bản trie.out một số nguyên duy nhất là số đỉnh có thể chọn làm gốc để thu được một cây Trie hoàn hảo.

Scoring

Sample Input 1

10
7 5 w
6 7 w
8 7 b
1 8 v
3 7 f
2 8 a
4 6 y
9 3 m
10 5 q

Sample Output 1

4

Notes

Các đỉnh thỏa mãn là các đỉnh ~5, 6, 4, 10~.