← 返回题目列表

AtCoder · discovery_2016_final_d

D. 迪斯科公司巡演二

中文机器翻译题面 查看原题

問題文

您是 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