Problem Description

You are the guide for the DISCO presents Discovery Channel Programming Contest 2016 Finals' DISCO Internal Tour.

The DISCO headquarters can be represented as a simple directed graph consisting of $ N $ vertices and $ M $ edges. The $ i $-th edge goes from $ from_i $ to $ to_i $ and is labeled either O or E.

The internal tour starts at some vertex $ s $ and can end at some vertex $ t $ when all edges in the graph satisfy the following conditions:

• If the edge is labeled O, it must be traversed an odd number of times.
• If the edge is labeled E, it must be traversed an even number of times (which can also be $ 0 $).

How many pairs of $ (s, t) $ are there such that the internal tour can be successfully completed?

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ from_1 $ $ to_1 $ $ label_1 $ $ . $ $ . $ $ . $ $ from_M $ $ to_M $ $ label_M $

• The first line contains two integers $ N $ and $ M $ representing the number of vertices and the number of directed edges, respectively $(2 \leq N \leq 200, 1 \leq M \leq N(N-1))$.
• The following $ M $ lines, where the $ i $-th line contains two integers $ from_i $ and $ to_i $ representing the edge information and a character $ label_i $ representing the edge label.
• $ label_i $ is either O or E.
• The given graph is a simple graph and does not contain multiple edges or self-loops.

Output Format

Output the number of pairs $ (s, t) $ that allow the internal tour to be completed in one line. Do not forget the newline at the end.

Sample Input and Output

Sample Input #1

2 1
1 2 O

Sample Output #1

1

Sample Input #2

2 1
1 2 E

Sample Output #2

2

Sample Input #3

4 2
1 2 O
3 4 E

Sample Output #3

1

Sample Input #4

4 2
1 2 O
3 4 O

Sample Output #4

0

Sample Input #5

3 3
1 2 O
2 3 O
3 1 O

Sample Output #5

3

Sample Input #6

4 5
1 2 O
2 1 O
2 3 O
3 1 E
2 4 O

Sample Output #6

1

Sample Input #7

4 3
1 2 O
2 1 O
3 4 E

Sample Output #7

2

Sample Input #8

2 2
1 2 O
2 1 E

Sample Output #8

2

Sample Input #9

4 3
1 2 O
1 3 O
1 4 O

Sample Output #9

0

Notes/Hints

Sample Explanation 1

• In this case, moving from vertex $ 1 $ to vertex $ 2 $ satisfies the condition. The answer is $ 1 $ way, which is $ (1, 2) $, and no other pairs exist.

Sample Explanation 2

• In this case, the condition is satisfied immediately after departure. The answer is $ 2 $ ways, which are $ (1, 1) $ and $ (2, 2) $, and no other pairs exist. Note that an edge labeled E can be traversed $ 0 $ times.

Sample Explanation 3

• In this case, moving from vertex $ 1 $ to vertex $ 2 $ satisfies the condition. The answer is $ 1 $ way, which is $ (1, 2) $, and no other pairs exist. Note that an edge labeled E can be traversed $ 0 $ times.

Sample Explanation 4

• In this case, no matter how you move, you cannot satisfy the condition. Note that an edge labeled O must be traversed an odd number of times, and an edge labeled E must be traversed an even number of times.

见题面 Input 部分

见题面 Output 部分