Breed Assignment

题目描述:

FJ 有 N 头牛，共三种品种，每头牛有可能是三种品种之一。不幸的是，FJ 忘记了哪头牛是哪个品种，它只记得一些两头牛的关系。现在给定 K 个头系，求每头是哪个品种的所有可能情况。

输入格式:

第一行包括两个整数 N 和 K。 以下 K 行，每行第一个为字母 D 或 S，紧接着两个整数 X 和 Y。D 表示 X 和 Y 不同品种，S 表示 X 和 Y 同一品种。保证 X 不等于 Y。

输出格式:

输出所有可能情况。如果有相互矛盾的情况，则输出 0。

样例输入:

4 2
S 1 2
D 1 3

样例输出:

18

提示:

样例解释：

前三个有 6 种可能情况，第 4 个有三种可能情况，总共有 18 种可能情况。

数据范围：

2 <= N <= 15
1 <= K <= 50
1 <= X,Y <= N
时间限制: 1000ms
空间限制: 256MB
求代码+讲解