C++ :

#include <bits/stdc++.h>
using namespace std;
int n,k,tot[20],cl[20];
char a[20][20];
long long ans;
int pd(int x,int co)
{
	for (int i=1;i<=n;i++){
		if (cl[i] && a[i][x] == 'S' && cl[i]!=co) return 0;
		if (cl[i] && a[i][x] == 'D' && cl[i]==co) return 0;
	}
	return 1;
}
void  dfs(int t)
{
	while (!tot[t]) t++;
	if (t > n){
		ans++;return;
	}
	for (int i=1;i<=3;i++){
		if (pd(t,i)){
			cl[t]=i;
			dfs(t+1);
			cl[t]=0;
		}
	}
}
int main()
{
	cin >> n >> k;
	for (int i=1;i<=k;i++){
		char c;
		int x,y;
		cin>> c>>x>>y;
		a[x][y]=c;a[y][x]=c;
		tot[x]++;tot[y]++;
	}
	//cout<<tot[1]<<tot[2]<<tot[3]<<tot[4];
	dfs(1);
	for (int i=1;i<=n;i++)
	   if (!tot[i]) ans=ans*3;
	cout << ans;
	return 0;
}