Valid Trie Roots

A trie is a rooted tree with n vertices and n-1 edges, where each edge is marked with a character. Each vertex x represents a string s(x) defined as follows:

• The root represents the empty string.
• If vertex u is the parent of vertex v and the edge connecting them is labeled with character c, then s(v)=s(u)+c (where the + denotes concatenation).

A trie is valid if every vertex represents a distinct string. In a rooted tree the string of a vertex is defined by the unique simple path from the root. Thus, a conflict happens if a vertex has at least two children edges with the same label (because both children will have an identical string, namely s(u)+c).

You are given an unrooted tree with n vertices and n-1 edges. Each edge comes with an associated character. If you choose a vertex as the root and direct each edge away from the root, then each vertex (except the root) will have a "parent edge" into it and a number of "child edges". The vertex v (with v ≠ root) is allowed to have a duplicate label only if the duplicate occurs in the parent edge. More formally, if a vertex v has an incident edge label that appears twice in total, then it is valid as a non-root only if one of those occurrences is the edge coming from its parent. Meanwhile, if a vertex is chosen as the root, then all edge labels incident on it (all its children) must be distinct.

Your task is to determine how many vertices you can select as the root so that when the tree is rooted at that vertex the trie becomes valid (i.e. every vertex represents a distinct string).

Note: For each vertex v, let freq(v, c) be the frequency of character c among all edges incident to v (since the tree is undirected). Then, for a candidate rooting:

• If v is chosen as the root then freq(v, c) ≤ 1 for every character c.
• If v is not the root and the edge from its parent is labeled p, then we require that freq(v, p) ≤ 2 (so that after removing the parent edge one occurrence remains) and for any other character c ≠ p, freq(v, c) ≤ 1.

Output the number of valid choices for the root.

inputFormat

The first line contains an integer n (1 ≤ n ≤ N), the number of vertices.

Each of the next n-1 lines describes an edge with three items: two integers u and v (1 ≤ u,v ≤ n representing the endpoints) and a lowercase letter c indicating the label on the edge.

The vertices are numbered from 1 to n.

outputFormat

Output a single integer – the number of vertices that can be selected as the root so that the tree becomes a valid trie.

sample

3
1 2 a
1 3 a

2