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 翻译