题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4945
分析：
首先考虑没有x的情况，发现有一个明显的推理模型，容易看出来可以用2-SAT做。
然后考虑有x的情况，发现最多只有8个x，不难想到可以搜索每个x为a,b,c中的哪个然后跑2-SAT。但是算算时间发现会T。
再仔细分析，发现只需要枚举两种情况就可以了。因为可行的对象已经全部在这两种情况里面包含了！
发现真的tarjan比另外一个算法快......事实证明另外一个算法（我叫不出名字ORZ）是可以被卡成O(NM)的。（从此入了tarjan的教。。。）
此题细节令人开心。
时间复杂度O((N+M)*2^x)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
const int maxn=;
const int maxm=; int N,D,M;
char S[maxn];
struct edge{ int to,next; }E[maxm<<];
struct data{ int i,j; char hi,hj; }da[maxm];
int first[maxn<<],_first[maxn<<],np,pos[],cnt,stk[maxn<<],top;
int dfn[maxn<<],sccno[maxn<<],dfs_clock,scc_cnt,low[maxn<<];
bool bad[maxn<<],_bad[maxn<<]; void _scanf(int &x)
{
x=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
void _scanf(char &x)
{
x=getchar();
while(!isalpha(x)) x=getchar();
}
void add_edge(int u,int v,int *f)
{
E[++np]=(edge){v,f[u]};
f[u]=np;
}
int id(int i,char a)
{
if(S[i]=='a') return i*-(a=='B'?:);
return i*-(a=='A'?:);
}
int _id(int i,bool k)
{
if(k) return S[i]=='a'?:;
return S[i]=='c'?:;
}
void data_in()
{
_scanf(N);_scanf(D);scanf("%s",S+);_scanf(M);
int a,b; char hi,hj;
for(int i=;i<=N;i++)
if(S[i]=='x') pos[++cnt]=i;
cnt=;
for(int i=;i<=M;i++){
_scanf(a);_scanf(hi);_scanf(b);_scanf(hj);
if(S[a]-hi==) continue;
if(S[a]=='x'||S[b]=='x'){
da[++cnt]=(data){a,b,hi,hj};
continue;
}
if(S[b]-hj==){ bad[id(a,hi)]=; continue; }
a=id(a,hi),b=id(b,hj);
add_edge(a,b,first); add_edge((b-^)+,(a-^)+,first);
}
}
void tarjan_scc(int i)
{
if(_bad[i]) return;
dfn[i]=low[i]=++dfs_clock;
stk[++top]=i;
for(int p=_first[i];p;p=E[p].next){
int j=E[p].to;
if(dfn[j]){
if(!sccno[j]) low[i]=min(low[i],dfn[j]);
continue;
}
tarjan_scc(j);
low[i]=min(low[i],low[j]);
}
if(low[i]==dfn[i]){
scc_cnt++;
while(stk[top]!=i) sccno[stk[top--]]=scc_cnt;
sccno[stk[top--]]=scc_cnt;
}
}
bool judge()
{
memset(dfn,,sizeof(dfn));
memset(sccno,,sizeof(sccno));
memset(low,,sizeof(low));
dfs_clock=scc_cnt=top=;
for(int i=;i<=N*;i++)
if(!dfn[i]) tarjan_scc(i);
for(int i=;i<=N;i++)
if(sccno[i*-]==sccno[i*]) return ;
return ;
}
bool run(int i)
{
if(i>D){
memcpy(_first,first,sizeof(first));
memcpy(_bad,bad,sizeof(bad));
int tmp=np,a,b;
for(int k=;k<=cnt;k++){
if(S[da[k].i]-da[k].hi==) continue;
if(S[da[k].j]-da[k].hj==){ _bad[id(da[k].i,da[k].hi)]=; continue; }
a=id(da[k].i,da[k].hi),b=id(da[k].j,da[k].hj);
add_edge(a,b,_first); add_edge((b-^)+,(a-^)+,_first);
}
np=tmp;
return judge();
}
S[pos[i]]='a'; if(run(i+)) return ;
S[pos[i]]='b'; if(run(i+)) return ;
return ;
}
void work()
{
if(!run()) printf("%d\n",-);
else{
for(int i=;i<=N;i++){
if(!sccno[i*-]) putchar('A'+_id(i,));
else if(!sccno[i*]) putchar('A'+_id(i,));
else if(sccno[i*]<sccno[i*-]) putchar('A'+_id(i,));
else putchar('A'+_id(i,));
}
putchar('\n');
}
}
int main()
{
data_in();
work();
return ;
}