#2、奶牛

#2、奶牛

Description

Farmer John 有N 头奶牛(2 <= N <= 15),每头奶牛属于下面三个品种中的一个:Holsteins 荷斯坦牛, Jerseys 泽西种乳牛, Guernseys 格恩西种奶牛。不幸的是,Farmer John 记不清他的奶牛们确切的品种。但是,他记得奶牛们之间K 个关系的名单(1 <= K <= 50)。例如,他记得,奶牛1 和奶牛2 有相同的品种,奶牛1 和奶牛5 是不同的品种。现在给Farmer John 一个奶牛们之间K 个关系的列表,请帮助他计算不同情况下奶牛们的品种的情况个数(如果列表中包含矛盾的信息,那么这个数可能为0)

Format

Input

第1 行:两个空格隔开的整型数:N 和K。
第2 ..1+K 行:每行描述了奶牛x 和奶牛y 之间的关系(1 <= x,y <= N, x != y)。
形如“S x y”表示x 和y 有着相同的品种,形如“D x y”表示x 和y 是不同的品种。

Output

一行,为可能的品种安排情况个数。

Sample 1

Input

4 2
S 1 2
D 1 3

Output

18

【样例解释】
现在有4 头奶牛。奶牛1 和奶牛2 是相同的品种,奶牛1 和奶牛3 是不同的品种。
下面六种品种安排情况是前3 头奶牛的情况:HHG,HHJ,GGH,GGJ,JJH,JJG。在每种
情况下,我们可以有3 种品种安排给第4 头奶牛,则根据列表总共有18 种不同的品种
安排方式。