2553: 奶牛品种
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：16
解决：2
题目描述
Farmer John有N头奶牛(2 <= N <= 15)，每头奶牛属于下面三个品种中的一个：
Holsteins荷斯坦牛, Jerseys泽西种乳牛, Guernseys格恩西种奶牛。
不幸的是，Farmer John记不清他的奶牛们确切的品种。但是，他记得奶牛们之间
K个关系的名单(1 <= K <= 50)。例如，他记得，奶牛1和奶牛2有相同的品种，奶牛
1和奶牛5是不同的品种。
现在给Farmer John一个奶牛们之间K个关系的列表，请帮助他计算不同情况下奶
牛们的品种的情况个数（如果列表中包含矛盾的信息，那么这个数可能为0）
输入
第1行：两个空格隔开的整型数：N和K。
第2 ..1+K行：每行描述了奶牛x和奶牛y之间的关系(1 <= x,y <= N, x != y)。
形如“S x y”表示x和y有着相同的品种，形如“D x y”表示x和y是不同的品
种。
输出
一行，为可能的品种安排情况个数。
样例输入 复制
4 2
S 1 2
D 1 3样例输出 复制
18提示
【样例解释】
现在有4头奶牛。奶牛1和奶牛2是相同的品种，奶牛1和奶牛3是不同的品种。
下面六种品种安排情况是前3头奶牛的情况：HHG，HHJ,GGH,GGJ,JJH,JJG。在每种
情况下，我们可以有3种品种安排给第4头奶牛，则根据列表总共有18种不同的品种
安排方式。