输入格式

程序告诉你了一堆关系(同组/不同组)。总共有3组。

第1行:n(表示团队里总共有多少人),k(表示@i_am_aking_ioi程序告诉你的k组关系) 接下来k行,每行表示一个关系。

S x y: x和y是同组的(1 <= x,y <= n, x != y)

D x y: x和y是不同组的。

输出格式

求名单总共有多少种可能性。

输入输出样例

输入 #1复制

5 5
D 1 3
S 2 1
D 1 5
D 5 4
D 5 3
输出 #1复制
12

说明/提示

1<=x,y<=n,x!=y

n<=15,k<=50

对于测试点1~2,n<=4,k<=2。

对于测试点1~3,n<=5,k<=5。

对于测试点1~4,7,8,ans<=100。此处ans表示输出的答案(即方案数)。

对于测试点1~8,ans<=1000。

对于测试点1~2,9 k<=2。

对于测试点1~3,9 k<=5。