AT_discovery_2016_final_d ディスコ社内ツアーⅡ

[problemUrl]: https://atcoder.jp/contests/discovery2016-final/tasks/discovery_2016_final_d あなたは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 $ 行に出力せよ。末尾の改行を忘れないこと。

### Sample Explanation 1 \- このケースにおいては頂点 $ 1 $ から頂点 $ 2 $ に向かって移動したとき、条件を満たします。答えは $ (1,2) $ の $ 1 $ 通りであり、それ以外には存在しません。 ### Sample Explanation 2 \- このケースにおいては出発直後に条件を満たしています。答えは $ (1,1),\ (2,2) $ の $ 2 $ 通りであり、それ以外には存在しません。 - `E`のラベルがついた辺は $ 0 $ 回通ってもよいことに注意してください。 ### Sample Explanation 3 \- このケースにおいては頂点 $ 1 $ から頂点 $ 2 $ に向かって移動したとき、条件を満たします。答えは $ (1,2) $ の $ 1 $ 通りであり、それ以外には存在しません。 - `E`のラベルがついた辺は $ 0 $ 回通ってもよいことに注意してください。 ### Sample Explanation 4 \- このケースにおいては、どのように移動しても条件を満たすことはできません。 - `O`のラベルがついているような辺はそれぞれ奇数回通らなくてはならないこと、`E`のラベルがついているような辺はそれぞれ偶数回通らなくてはならないことに注意してください。