Cyber hack#11149
Vi attempts to hack into the Arasaka Corporation's servers in order to disable the security and infiltrate their office. The artificial intelligence of the server is trying to prevent her from doing this.
Hacking occurs as follows. Consider a directed graph, each edge of which contains a letter of the English alphabet. A graph can contain multiple edges and even loops. Vi has a token initially located at some node and the server AI has a token initially located at some node . Then they take turns making moves, Vi goes first. On her move, Vi chooses an arbitrary edge outgoing from the vertex where her token is located. Vi moves the token along that edge and also tries to perform an attack like , where is the character written on the selected edge. The AI on its turn also selects one of the edges coming from the vertex where its token is located and moves the token along that edge. At the same time, in order to successfully repel the attack, it must choose an edge on which the same symbol is written.
If Vi can't make a move because no edge comes out of the vertex where her token is located, the hack fails. If the AI cannot choose an edge coming from the vertex where its token is located, on which the character is written, the hack succeeds. Also, a situation is possible in which Vi and AI will make moves indefinitely.
Help Vi determine the number of start states, that is, pairs of and vertices, in which the hacking will be successful under the optimal actions of Vi and AI.
The first line contains two integers and (1 \leq n \leq 1000, 0 \leq m \leq 1000) - the number of vertices and edges in the graph.
The following lines describe the graph's edges. Each line contains two integers a_i and b_i and a lowercase English letter c_i, they represent an edge from node a_i to node b_i with c_i character (1 \leq a_i, b_i \leq n).
Print a single number - the desired number of starting states.
Example 1
Example 2
In the first example, if initially the Vi and AI tokens are in the same node, the process will never end. In all other cases, hacking will be successful.