Description：

有 $n$ 个未知数， $m$ 个方程组，方程组有两种： $gcd(x_i,x_j)=k$ 或 $lcm(x_i,x_j)=k$ ，判断方程组是否有解。

$1\le n,m\le 200$

Solution：

$gcd$ 和 $lcm$ 可以通过指数取 $max/min$ 来计算，可以把每个数拆成所有素因子，每个素因子再拆成所有指数，即变量 $s[i][j][k]$ 表示 $p_j^k$ 是否整除 $x_i$ ，那么 $s[i][j][1]$ 即代表 $x_i$ 是否含有 $p_j$ 这个素因子，通过这种方法可以把问题转化成一个 $2-SAT$ 问题，显然必须连边 $s[i][j][k]\to s[i][j][k-1]$ ， $\lnot s[i][j][k-1]\to \lnot s[i][j][k]$ 分类讨论：

$1$ 、 $gcd$

对于没有出现在 $gcd$ 中的每个素数 $p_k$ ，他们要么没有出现，要么只出现在了 $x_i$ 或 $x_j$ 中，于是连边 $s[i][k][1]\to\lnot s[j][k][1]$ ， $s[j][k][1]\to\lnot s[i][k][1]$ 。

对于出现过的素数 $p_k$ ，设他的指数为 $w$ ，首先必须要强制 $s[i][k][w]$ 和 $s[j][k][w]$ 为真，他的对应变量为假，只要把假向真连一条边即可，因为这样如果假那么真，所以假一定不合法，所以一定真，然后他的更高次幂一定只在一个数中出现，于是连边 $s[i][k][w+1]\to \lnot s[j][k][w+1]$ ， $s[j][k][w+1]\to\lnot s[i][k][w+1]$ 。

$2$ 、 $lcm$

对于没有出现在 $lcm$ 中的每个素数 $p_k$ ，他们一定没有出现，于是强制 $s[i][k][1]$ 和 $s[j][k][1]$ 为假，只要把真向假连一条边即可。

对于出现了的素数 $p_k$ ，设他的指数为 $w$ ，强制 $s[i][k][w+1]$ 和 $s[j][k][w+1]$ 为假，还要保证一定至少有一个 $w$ 为真，于是 $\lnot s[i][k][w]\to s[j][k][w]$ ， $\lnot s[j][k][w]\to s[i][k][w]$ 。

然后只要判断 $s[i][j][k]$ 和 $\lnot s[i][j][k]$ 不在同一强连通分量里即可。

切记每一个 $testcases$ 要把该清零的清零。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<set>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 210

char getc()

{

	char c = getchar();

	while(c != 'L' && c != 'G')c = getchar();

	return c;

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

#define MAX 1000000000

map<int,map<int,map<int,map<int,int> > > > s;

int ptr = 0;

#define MAXD 1000000

#define MAXE 10000000

struct edge

{

	int to,nxt;

}e[MAXE];

int edgenum = 0;

int lin[MAXD];

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int dfn[MAXD],low[MAXD],cnt = 0;

int ins[MAXD],scc = 0;

bool v[MAXD];

stack<int> st;

void tarjan(int k)

{

	dfn[k] = low[k] = ++cnt;

	v[k] = true;st.push(k);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	if(dfn[k] == low[k])

	{

		++scc;

		int t;

		do

		{

			t = st.top();st.pop();

			ins[t] = scc;v[t] = false;

		}while(t != k);

	}

	return;

}

char c[MAXN];

int a[MAXN],b[MAXN],t[MAXN];

set<int> prime;

map<int,int> p;

map<int,int> times;

int tot = 0;

void work()

{

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	prime.clear();p.clear();tot = 0;s.clear();

	scanf("%d%d",&n,&m);

	int w;

	for(int i = 1;i <= m;++i)

	{

		c[i] = getc();a[i] = read();b[i] = read();t[i] = read();++a[i];++b[i];

		w = t[i];

		for(int j = 2;j * j <= t[i];++j)

		{

			if(w % j == 0)

			{

				if(prime.find(j) == prime.end())

					prime.insert(j);

				while(w % j == 0)w /= j;

			}

		}

		if(w != 1)

			if(prime.find(w) == prime.end())

				prime.insert(w);

	}

	for(set<int>::iterator it = prime.begin();it != prime.end();++it)

	{

		p[++tot] = *it;

		times[tot] = log2(MAX) / log2(*it);

	}

	ptr = 0;

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= tot;++j)

			for(int k = 1;k <= times[j];++k)

				s[i][j][k][1] = ++ptr,s[i][j][k][0] = ++ptr;

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= tot;++j)

			for(int k = 2;k <= times[j];++k)

				add(s[i][j][k][1],s[i][j][k - 1][1]);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= tot;++j)

			for(int k = 2;k <= times[j];++k)

				add(s[i][j][k - 1][0],s[i][j][k][0]);

	for(int i = 1;i <= m;++i)

	{

		if(c[i] == 'G')

		{

			for(int k = 1;k <= tot;++k)

			{

				if(t[i] % p[k] == 0)

				{

					int cnt = 0;

					int y = t[i];while(y % p[k] == 0){++cnt;y /= p[k];}

					add(s[a[i]][k][cnt][0],s[a[i]][k][cnt][1]);

					add(s[b[i]][k][cnt][0],s[b[i]][k][cnt][1]);

					add(s[a[i]][k][cnt + 1][1],s[b[i]][k][cnt + 1][0]);

					add(s[b[i]][k][cnt + 1][1],s[a[i]][k][cnt + 1][0]);

				}

				else

				{

					add(s[a[i]][k][1][1],s[b[i]][k][1][0]);

					add(s[b[i]][k][1][1],s[a[i]][k][1][0]);

				}

			}

		}

		else

		{

			for(int k = 1;k <= tot;++k)

			{

				if(t[i] % p[k] == 0)

				{

					int cnt = 0;

					int y = t[i];while(y % p[k] == 0){++cnt;y /= p[k];}

					add(s[a[i]][k][cnt][0],s[b[i]][k][cnt][1]);

					add(s[b[i]][k][cnt][0],s[a[i]][k][cnt][1]);

					add(s[a[i]][k][cnt + 1][1],s[a[i]][k][cnt + 1][0]);

					add(s[b[i]][k][cnt + 1][1],s[b[i]][k][cnt + 1][0]);

				}

				else

				{

					add(s[a[i]][k][1][1],s[a[i]][k][1][0]);

					add(s[b[i]][k][1][1],s[b[i]][k][1][0]);

				}

			}

		}

	}

	memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));cnt = 0;scc = 0;

	for(int i = 1;i <= ptr;++i)if(dfn[i] == 0)tarjan(i);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= tot;++j)

		{

			for(int k = 1;k <= times[j];++k)

			{

				if(ins[s[i][j][k][1]] == ins[s[i][j][k][0]])

				{

					puts("Solution does not exist");

					return;

				}

			}

		}

	}

	puts("Solution exists");

	return;

}

int main()

{

	int testcases = 0;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}