← 返回题目列表

AtCoder · kupc2021_k

K. 三色

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

配点 : 400 点

問題文

N 墙。将每面墙涂成红色、绿色或蓝色 1 考虑用颜色绘画。 给出了

M 条件。 第i 个条件是整数 a_i,b_i 和字符 x_i,y_i ,

  • 壁 a_i 颜色 当涂上 x_i 时,墙壁 请勿使用 b_i 颜色 当涂上 y_i 进行绘画

。然而, x_i,y_i 是一个字符 R , G , B ,以及 R 当红色时,G 当绿色时, B 代表蓝色。

M 请告诉我有多少种方法来绘制满足所有条件的颜色。

制約

  • 1 \leq N \leq 22
  • 0 \leq M \leq 9 \times \frac{N(N-1)}{2}
  • 1 \leq a_i < b_i \leq N
  • x_i,y_i 是一个字符 R , G , B 。
  • i \neq j 时,(a_i,x_i,b_i,y_i) \neq (a_j,x_j,b_j,y_j)
  • N,M,a_i,b_i 均为整数 当把

入力

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

N M
a_1 x_1 b_1 y_1
\vdots
a_M x_M b_M y_M

出力

答案 打印除以 1 按行输出。


入力例 1

2 3
1 R 2 R
1 G 2 R
1 B 2 G

出力例 1

6

壁 1 涂成红色时,墙壁 2 可以涂成绿色或蓝色。 当把

壁 1 涂成绿色时,墙壁 当用蓝色绘制 2 可以涂成绿色或蓝色。 当把

壁 1 时,墙壁 2 可以涂成红色或蓝色。 因此,总共 6 绘画有不同的方法。 使用任何颜色绘制


入力例 2

1 0

出力例 2

3

壁 1 即可满足条件。


入力例 3

22 0

出力例 3

31381059609

小心溢出。


入力例 4

4 12
2 R 3 R
1 B 2 B
2 R 3 B
3 R 4 R
1 B 4 G
1 R 3 B
3 G 4 B
2 G 3 G
1 B 2 R
1 G 2 R
1 R 3 G
1 G 3 B

出力例 4

13