#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int c, t;
int n, m;
//最后会变成谁或非谁（用对应负数表示非），0 表示和所有人初始值没关系 
int x[MAXN + 5];
//如果 x[i] 为 0，val[i] 表示会变成多少 
char val[MAXN + 5]; 
char myNot(char x)
{
	if (x == 'T')
		return 'F';
	if (x == 'F')
		return 'T';
	return 'U';	
} 
//n,m <= 10 
namespace subtask1{
	char ini[MAXN + 5]; //初始值设置的值
	char temp[MAXN + 5]; //最终推理的值 
	int ans;
	void dfs(int now,int cnt)
	{
		if (now == n + 1)
		{
			//验证 
			for(int i = 1; i <= n; i++)
			{
				if(x[i] == 0)
					temp[i] = val[i];
				else if(x[i] > 0)
					temp[i] = ini[x[i]];
				else if(x[i] < 0)
					temp[i] = myNot(ini[-x[i]]);
			} 
			bool flag = true;
			for(int i = 1; i <= n; i++)
				if (ini[i] != temp[i])
				{
					flag=false;
					break;
				}
			if (flag)
				ans = min(ans, cnt);
			return ;
		}
		ini[now] = 'T';
		dfs(now+1, cnt);
		ini[now] = 'F';
		dfs(now+1, cnt);
		ini[now] = 'U';
		dfs(now+1, cnt+1);
	}
	void main()
	{
		ans = n;
		dfs(1, 0);
		cout << ans << "\n"; 
	} 
}
//没有依赖 
namespace subtask2{
	void main()
	{
		int ans = 0;
		for(int i = 1; i <= n; i++) 
			if (x[i] == 0 && val[i] == 'U') 
				ans++;
		cout << ans << "\n";
	}
}
//没有 - 
namespace subtask3{
	bool vis[MAXN + 5];
	char f(int pos)
	{
		vis[pos] = true;
		//如果当前为定值，返回对应值 
		if (x[pos] == 0)
			return val[pos];
		//如果出现了环，这条路上都设置为真 
		if (vis[x[pos]] == true && 
			x[x[pos]] != 0){
				
			x[pos] = 0;
			val[pos] = 'T';
			return 'T';
		}
		val[pos] = f(x[pos]);
		x[pos] = 0;	
		return val[pos];
	}
	void main()
	{
		//推理最终值 
		int ans = 0;
		for(int i = 1; i <= n; i++)
			vis[i] = false;
		for(int i = 1; i <= n; i++) 
		{ 
			if (f(i) == 'U')
				ans++;
		} 
		cout << ans << "\n";
	}
}
//并查集，合并与某个数初值相等及不等的位置 
namespace subtask4{
	int tot, p[MAXN+5][2];//p[i][0] 和 i 相等的点、p[i][1] 和 i 不等的点 
	int fa[MAXN * 2 + 10];
	int findFa(int x)
	{
		if(x == fa[x])
			return x;
		return fa[x] = findFa(fa[x]);	
	}
	void mer(int x,int y)
	{
		int faX = findFa(x);
		int faY = findFa(y);
		fa[faX] = faY;
	}
	void main()
	{
		//给点编好号 
		tot = 0;
		for(int i = 1; i <= n; i++) 
		{
			p[i][0] = ++tot;
			p[i][1] = ++tot;
		}
		//把相等关系与不等关系通过并查集加上去
		for(int i = 1; i <= tot; i++)
			fa[i] = i;
		for(int i = 1; i <= n; i++)
		{
			if(x[i] == 0)
			{
				if(val[i] == 'U')
					mer(p[i][0], p[i][1]);
			}
			else if(x[i] > 0)
			{
				mer(p[i][0], p[x[i]][0]);
				mer(p[i][1], p[x[i]][1]);
			}			
			else if(x[i] < 0)
			{
				mer(p[i][0], p[-x[i]][1]);
				mer(p[i][1], p[-x[i]][0]);
			}
		}
		//输出要有几个 U 
		int ans = 0;
		for(int i = 1; i <= n; i++)
			if(findFa(p[i][0]) == findFa(p[i][1]))
				ans++;
		cout << ans << "\n";
	}
}
int main()
{
	freopen("tribool.in", "r", stdin);
	freopen("tribool.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> c >> t;
	while (t--)
	{
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
			x[i] = i;
		while (m--)
		{
			char v;
			int posI, posJ;
			cin >> v;
			if (v == 'T' || v == 'F' || v == 'U')
			{
				cin >> posI;
				x[posI] = 0;
				val[posI] = v;				
			}
			else if (v == '+')
			{
				cin >> posI >> posJ;
				if (x[posJ] != 0)
					x[posI] = x[posJ];				
				else
				{
					x[posI] = 0;
					val[posI] = val[posJ];	
				}
			}
			else if (v == '-')
			{
				cin >> posI >> posJ;
				if (x[posJ] != 0)
					x[posI] = -x[posJ];				
				else
				{
					x[posI] = 0;
					val[posI] = myNot(val[posJ]);	
				}	
			}
		}	
		if(c <= 2)
			subtask1::main();
		else if(c <= 4)
			subtask2::main();
		else if(c <= 6)
			subtask3::main();
		else
			subtask4::main();
	}	
	return 0;
}