AC代码，hack数据第一个点跑1.99s。

#include<bits/stdc++.h> 
using namespace std;
int n,d,m,id,scc[100005];
char ans[50005],ns[50005];
char yu[5][5]={"BC","AC","AB"};
string s;
struct node{
	int i,j;
	char hi[5],hj[5];
};
bool vis[100005];
node vec[100005];
vector<int>plc,g[100005],g2[100005];
vector<int>sk;
void dfs1(int u){
    vis[u]=1;
    for(auto v:g[u]){
        if(!vis[v])dfs1(v);
    }
    sk.push_back(u);
}//第一遍dfs
void dfs2(int u){
    scc[u]=id;
    for(auto v:g2[u]){
        if(!scc[v])dfs2(v);
    }
}//建反图跑第二遍dfs
//kosarajo
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>d>>s>>m;
	s=' '+s;
	for(int i=1;i<=n;i++){
		if(s[i]=='x')plc.push_back(i);
		else ns[i]=s[i];
	}
	for(int i=1;i<=m;i++){
		cin>>vec[i].i>>vec[i].hi>>vec[i].j>>vec[i].hj;
	}
	for(int msk=0;msk<(1<<d);msk++){
		fill(vis+1,vis+1+2*n,0);
		fill(scc+1,scc+1+2*n,0);
		sk.clear();
		id=0;
		for(int i=1;i<=2*n;i++)g[i].clear(),g2[i].clear();
		for(int i=0;i<d;i++){
			if(msk&(1<<i))ns[plc[i]]='a';
			else ns[plc[i]]='b';
		}
		for(int x=1;x<=m;x++){
   			int i=vec[x].i,j=vec[x].j;
   			int vi=ns[i]-'a',vj=ns[j]-'a';
   			int u1=i+n*(vec[x].hi[0]!=yu[vi][0]),v1=j+n*(vec[x].hj[0]!=yu[vj][0]);
   			int u2=(u1>n?u1-n:u1+n),v2=(v1>n?v1-n:v1+n);
   			if(vec[x].hi[0]-'A'==vi)continue;
   			if(vec[x].hj[0]-'A'==vj){
   				g[u1].push_back(u2);
   				g2[u2].push_back(u1);
			}else{
    			g[u1].push_back(v1);
    			g2[v1].push_back(u1);
    			g[v2].push_back(u2);
    			g2[u2].push_back(v2);
   			}
  		}//毒瘤建图
  		for(int i=1;i<=2*n;i++){
        	if(!vis[i])dfs1(i);
    	}
    	for(int i=sk.size()-1;i>=0;i--){
        	int v=sk[i];
        	if(!scc[v]){
         	    id++;
         	    dfs2(v);
        	}
    	}
    	bool flag=1;
    	for(int i=1;i<=n;i++){
    		if(scc[i]==scc[i+n]){
    			flag=0;
    			break;
			}
		}
    	if(flag){
   			for(int i=1;i<=n;i++){
   				if(scc[i]>scc[i+n]){
     				if(ns[i]=='a')cout<<'B';
     				else cout<<'A';
    			}
    			else{
     				if(ns[i]!='c')cout<<'C';
     				else cout<<'B';
    			}
			}
			return 0;
  		}
	}
	cout<<-1;
}

鉴于这道题太恶心了我C遍了TJ也找不到一个用kosarajo的，仅供参考