来复习( ext{2-sat})了
首先对于(operatorname{'a'}, m{'b'}, m{'c'})这三种地图，能放在上面的车只有两种
但是对于( m{'x'})能放三种车，变成一个( ext{3-sat})
众所周知( ext{3-sat})只能搜索，于是我们爆搜这个位置放什么车
剩下的我们还是直接用( ext{2-sat})来判定
对于一组限制(u,h_i,v,h_j)，如果(u)上不能放(h_i)这辆车，那么这个操作就不用处理了
如果(v)上不能放(h_j)这辆车，那么就让(u->u')，表示一旦选择(u)就不合法了
否则我们就正常连边，连(u->v)，表示选择(h_i)就必须选(h_j)；最重要的是，根据对称性，我们还得连(v'->u')，表示不选(h_j)就不能选(h_i)
这样做的复杂度是(O(3^d(n+m))) ，不大可行
考虑我们爆搜的时候不搜('x')放什么车了，改为搜('x')不放什么车，不放(A)车，那么就能放(B)车和(C)车；不放(B)车就能放(A)车和(C)车；所以我们只搜这个位置填成(a)还是(b)就把三种情况都计算了
于是复杂度(O(2^d(n+m)))
代码
#include<bits/stdc++.h>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=1e5+5;
char S[maxn],opv[maxn],opu[maxn];
struct E{int v,nxt;}e[maxn*3];
int u[maxn],v[maxn],tot,pos[15];
int head[maxn],n,m,num,d,__,top,cnt;
int dfn[maxn],col[maxn],low[maxn],st[maxn],f[maxn],id[2][maxn];
inline void add(int x,int y) {
e[++num].v=y;e[num].nxt=head[x];head[x]=num;
}
void tarjan(int x) {
dfn[x]=low[x]=++__,f[x]=1,st[++top]=x;
for(re int i=head[x];i;i=e[i].nxt)
if(!dfn[e[i].v]) tarjan(e[i].v),low[x]=min(low[x],low[e[i].v]);
else if(f[e[i].v]) low[x]=min(low[x],dfn[e[i].v]);
if(dfn[x]==low[x]) {
++cnt;int now;
do{now=st[top--];col[now]=cnt;f[now]=0;}while(now!=x);
}
}
inline int getid(int i,char c) {
if(S[i]==c+'a'-'A') return -1;
if(S[i]=='a') return c=='B'?0:1;
if(S[i]=='b') return c=='C'?0:1;
if(S[i]=='c') return c=='A'?0:1;
}
inline void put(int i,int c) {
if(S[i]=='a') putchar(c?'C':'B');
if(S[i]=='b') putchar(c?'A':'C');
if(S[i]=='c') putchar(c?'B':'A');
}
inline void solve() {
cnt=__=0;num=0;memset(head,0,sizeof(head));top=0;
memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
memset(col,0,sizeof(col));memset(f,0,sizeof(f));
for(re int i=1;i<=m;i++) {
int x=getid(u[i],opu[i]);
if(x==-1) continue;
int y=getid(v[i],opv[i]);
if(y==-1) {add(id[x][u[i]],id[x^1][u[i]]);continue;}
add(id[x][u[i]],id[y][v[i]]);
add(id[y^1][v[i]],id[x^1][u[i]]);
}
for(re int i=1;i<=n+n;i++) if(!dfn[i]) tarjan(i);
for(re int i=1;i<=n;i++) if(col[i]==col[i+n]) return;
for(re int i=1;i<=n;i++)
if(col[i]<col[i+n]) put(i,0);else put(i,1);
exit(0);
}
void dfs(int x) {
if(x==d+1) {solve();return;}
S[pos[x]]='a';dfs(x+1);
S[pos[x]]='b';dfs(x+1);
}
int main() {
n=read();d=read(),scanf("%s",S+1);m=read();
for(re int i=1;i<=m;i++) {
u[i]=read();std::cin>>opu[i];
v[i]=read();std::cin>>opv[i];
}
for(re int i=1;i<=n;i++) id[0][i]=i,id[1][i]=i+n;
for(re int i=1;i<=n;i++) if(S[i]=='x') pos[++tot]=i;
dfs(1);puts("-1");return 0;
}