品种分配

题目描述

农夫约翰有 $N$ 头奶牛，编号 $1\sim N$，每头都是以下三个品种之一：荷斯坦牛、泽西岛牛、根西岛牛。

不幸的是，约翰记不住他的奶牛们的确切品种。

但是，他有一个表中记录了 $K$ 对奶牛之间的关系，例如，奶牛 $1$ 和 $2$ 的品种相同，奶牛 $1$ 和 $5$ 的品种不同。

给定约翰记录的关系列表，请帮助约翰计算所有可能的奶牛品种分布情况的数量。

如果他记录的关系列表中有矛盾信息，则输出 $0$。

输入格式

第一行包含两个整数 $N$ 和 $K$。 接下来 $K$ 行，每行描述一对奶牛 $x$ 和 $y$ 之间的关系，`S x y` 表示两头奶牛品种相同，`D x y` 表示两头奶牛品种不同。

输出格式

输出可能的奶牛品种分布情况的数量。

4 2
S 1 2
D 1 3

18

提示

#### 数据范围 $2\le N\le 15,1\le K\le 50,1\le x,y\le N,x\ne y$ #### 样例解释 满足 $1$ 和 $2$ 相同品种，$1$ 和 $3$ 不同品种的前三头奶牛的品种分布情况为：$HHG,HHJ,GGH,GGJ,JJH,JJG$。 对于这 $6$ 种情况中的每一种，第四头奶牛都可以是 $3$ 种品种中的任意一种，所以一共有 $18$ 种不同的奶牛品种分布情况。

来源

童程童美