AT_kupc2021_k.Three Coloring

有 $N$ 面墙。现在要将每面墙涂成红色、绿色或蓝色中的一种颜色。

给出 $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 中的一个，分别表示红色、绿色和蓝色。

请计算满足所有 $M$ 个条件的涂色方案有多少种。

输入通过标准输入按以下格式给出：

$N$ $M$
$a_1$ $x_1$ $b_1$ $y_1$
$\vdots$
$a_M$ $x_M$ $b_M$ $y_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$ 均为整数

样例解释 1

当第 $1$ 面墙被涂成红色时，第 $2$ 面墙可以涂成绿色或蓝色。
当第 $1$ 面墙被涂成绿色时，第 $2$ 面墙可以涂成绿色或蓝色。
当第 $1$ 面墙被涂成蓝色时，第 $2$ 面墙可以涂成红色或蓝色。
因此，总共有 $6$ 种涂色方案。

样例解释 2

无论第 $1$ 面墙涂成哪种颜色，都能满足条件。

样例解释 3

请注意防止溢出。

由 ChatGPT 4.1 翻译