D - ディスコ社内ツアーⅡ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたはDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦のディスコ社内ツアーの案内人です。

ディスコ本社は 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
  • 1 行目に頂点数と有向辺の数を表す 2 つの整数 N, M (2≦N≦200, 1≦M≦N(N-1)) が与えられる。
  • 2 行目から続く M 行のうち i 行目には i 番目の辺の情報を表す 2 つの整数 from_i, to_i (1≦from_i,to_i≦N) と，辺についているラベルを表す文字 label_iが与えられる。
  • label_i はOまたはEのどちらかである。
  • 与えられるグラフは単純グラフであり、多重辺や自己ループを含まない。

出力

社内ツアーを終了することが可能な (s,t) の組み合わせの数を 1 行に出力せよ。末尾の改行を忘れないこと。

入力例 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のラベルがついた辺は 0 回通ってもよいことに注意してください。

入力例 3

4 2
1 2 O
3 4 E

出力例 3

1
  • このケースにおいては頂点 1 から頂点 2 に向かって移動したとき、条件を満たします。答えは (1,2) の 1 通りであり、それ以外には存在しません。
  • Eのラベルがついた辺は 0 回通ってもよいことに注意してください。

入力例 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