问题描述

你是DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦的导游。

DISCO总部由N个顶点和M条边组成，表示为一个简单有向图。第i条边从顶点from_i指向顶点to_i，并且标有标签O或E。

在满足以下条件的情况下，社内游可以从某个顶点s出发并在到达顶点t时结束：

• 如果边标有O，则该边被经过奇数次
• 如果边标有E，则该边被经过偶数次（可以是0次）

有多少种$(s,t)$的组合可以顺利完成社内游？

---

输入

输入以以下格式从标准输入中给出。

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

• 第一行包含两个整数$N, M (2 \leq N \leq 200, 1 \leq M \leq N(N-1))$，表示顶点数和有向边数。
• 接下来的M行中，第i行包含两个整数$from_i, to_i (1 \leq from_i, to_i \leq N)$，表示第i条边的信息，以及表示边标签的字符$label_i$。
• $label_i$为O或E。

输入的图是简单图，不包含重边和自环。

---

输出

输出社内游可以完成的$(s, t)$组合的数量，以一行输出。末尾不要忘记换行符。

---

示例 1

2 1
1 2 O

输出示例 1

1

在这个例子中，当从顶点1移动到顶点2时，满足条件。答案是$(1, 2)$有1种可能性，没有其他可能性。

---

示例 2

2 1
1 2 E

输出示例 2

2

在这个例子中，刚开始就满足条件。答案是$(1, 1), (2, 2)$有2种可能性，没有其他可能性。 请注意，标有E的边可以不经过任何次数。

---

示例 3

4 2
1 2 O
3 4 E

输出示例 3

1

在这个例子中，当从顶点1移动到顶点2时，满足条件。答案是$(1, 2)$有1种可能性，没有其他可能性。 请注意，标有E的边可以不经过任何次数。

---

示例 4

4 2
1 2 O
3 4 O

输出示例 4

0

在这个例子中，无论如何移动都无法满足条件。 请注意，标有O的边必须经过奇数次，标有E的边必须经过偶数次。

---

示例 5

3 3
1 2 O
2 3 O
3 1 O

输出示例 5

3

---

示例 6

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

输出示例 6

1

---

示例 7

4 3
1 2 O
2 1 O
3 4 E

输出示例 7

2

---

示例 8

2 2
1 2 O
2 1 E

输出示例 8

2

---

示例 9

4 3
1 2 O
1 3 O
1 4 O

输出示例 9

0

---