| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 1024 MB | 41 | 24 | 17 | 50.000% |
There are $N$ walls in the hall of the King's palace, numbered by integers from $1$ to $N$. The King asks the Royal Painter to paint each wall in one of three colors (red, green, or blue). Additionally, the King gives $M$ orders.
Every order has the following form: given two walls, $a_i$ and $b_i$, and two colors, $x_i$ and $y_i$, the order dictates that, if the wall $a_i$ is painted with color $x_i$ and the wall $b_i$ is painted with color $y_i$, the Royal Painter has to be executed.
Your task is to find a number of ways to paint the walls so that the Royal Painter will not be executed.
The first line of the input contains two integers $N$ and $M$ ($1 \le N \le 22$, $1 \le M \le 9 \cdot N \cdot (N-1)/2$): the number of walls and the number of orders, respectively.
Each of the following $M$ lines describes one King's order and contains an integer $a_i$, a letter $x_i$, an integer $b_i$, and a letter $y_i$, separated by single spaces ($1 \le a_i < b_i \le N$, $x_i$ and $y_i$ are letters from 'R', 'G', and 'B', denoting the red, green, and blue colors, respectively). You may assume that all $M$ orders are pairwise distinct (no two orders have the exact same effect).
Print one integer: the number of ways to paint the walls so that the Royal Painter will not be executed.
2 3 1 R 2 R 1 G 2 R 1 B 2 G
6
1 0
3
22 0
31381059609
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
13