King's Palace

면접 대비

시간 제한6초메모리 제한1024 MB

요약

N개의 벽을 3가지 색으로 칠할 때, 주어진 금지된 색 조합을 모두 피하는 경우의 수를 구한다. N은 최대 22이다.

난이도: 보통10점 중 6점
유형: 완전 탐색, 백트래킹, 비트 연산, 수학
정답자: 아직 제출이 없습니다

문제

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.

예제4

예제 1
입력
```
2 3
1 R 2 R
1 G 2 R
1 B 2 G
```
예상 출력
```
6
```
예제 2
입력
```
1 0
```
예상 출력
```
3
```
예제 3
입력
```
22 0
```
예상 출력
```
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

예상 출력