問題文
您是 DISCO 呈现探索频道编程大赛 2016 年主赛事 DISCO 内部巡演的导游。
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
- 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