0pts，思路与题解略有不同。

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int n,m,d,dfn[N],low[N],vis[N],cnt=0,scc[N],topo[N],x[N],y[N],a[N],b[N],sc=0;
string s;
vector<int>e[N];
stack<int>st;
void tarjan(int f,int x)
	{
	dfn[x]=low[x]=++cnt;vis[x]=1;st.push(x);
	for(int i=0;i<e[x].size();i++)
		{
		int d=e[x][i];
		if(!dfn[d])
			{
			tarjan(x,d);
			low[x]=min(low[x],low[d]);
			}
		else if(vis[d])low[x]=min(low[x],dfn[d]);
		}
	if(dfn[x]==low[x])
		{
		while(st.top()!=x)
			{
			int d=st.top();
			scc[d]=x;vis[d]=0;
			st.pop();
			}
		scc[x]=x;topo[x]=++sc;vis[x]=0;st.pop();
		}
	}
void work()
	{
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	memset(scc,0,sizeof scc);
	for(int i=1;i<=n;i++)e[i].clear();
	for(int i=1;i<=m;i++)
		{
		int d=s[i-1]-'a';
		if(d!=a[i])e[x[i]+n*(max(d,a[i])==1?2:min(d,a[i])==1?0:1)].push_back(y[i]+n*b[i]);
		}
	for(int i=1;i<=n*3;i++)
		{
		if(!dfn[i])tarjan(0,i);
		}
	for(int i=1;i<=n;i++)
		{
		int a1=scc[i],a2=scc[i+n],a3=scc[i+n*2];
		if(a1==a2||a1==a3||a2==a3)return;
		}
	for(int i=1;i<=n;i++)
		{
		int d=s[i-1]-'a';
		if(d==0)cout<<(topo[scc[i+n]]<topo[scc[i+n*2]]?'B':'C');
		else if(d==1)cout<<(topo[scc[i]]<topo[scc[i+n*2]]?'A':'C');
		else cout<<(topo[scc[i]]<topo[scc[i+n]]?'A':'B');
		}
	exit(0);
	}
void dfs(int v)
	{
	if(v==n+1){work();return;}
	if(s[v-1]!='x')dfs(v+1);
	else 
		{
		s[v-1]='a';dfs(v+1);
		s[v-1]='b';dfs(v+1);
		}
	}
int main()
	{
	cin>>n>>d>>s>>m;
	for(int i=1;i<=m;i++)
		{
		int xx,aa,yy,bb;char a1,b1;cin>>xx>>a1>>yy>>b1;
		aa=a1-'A';bb=b1-'A';
		x[i]=xx;y[i]=yy;a[i]=aa;b[i]=bb;
		}
	dfs(1);
	cout<<-1;
	return 0;
	}