Subtask2数据没过

#include<bits/stdc++.h>
using namespace std;

#define newline putchar('\n')
#define newspace putchar(' ')
#define ll long long
#define inf 1000000005
#define mod 998244353
#define eps 0.0000001
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define N 1000005

namespace fastIO {
    template<class T> void read(T &x) {
        x=0;
        int fl=1;
        char ch=getchar();
        while(ch<'0'||ch>'9') {
            if(ch=='-')fl=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9') {
            x=(x<<1)+(x<<3)+(ch&15);
            ch=getchar();
        }
        x*=fl;
    }
    template<class T> void read(T &x,T &y) {
        read(x);
        read(y);
    }
    template<class T> void read(T &x,T &y,T &z) {
        read(x);
        read(y);
        read(z);
    }
    template<class T> void write(T x) {
        if(x<0) {
            putchar('-');
            x=-x;
        }
        if(x/10)write(x/10);
        putchar(x%10+'0');
    }
    template<class T> void read(T *a,T n) {
        for(int i=1; i<=n; i++)read(a[i]);
    }
    template<class T> void write(T *a,T n) {
        for(int i=1; i<=n; i++)write(a[i]),newspace;
    }
}

using namespace fastIO;

namespace math {
    template<class T> ll fastpow(T a,T b,T md=1e18) {
        ll ans=1;
        for(; b; b>>=a,a=(a*a)%mod)if(b&1)ans=ans*a%md;
        return ans;
    }
    template<class T> ll A(T n,T m,T md=1e18) {
        ll ans1=1,ans2=1;
        for(int i=1; i<=n-m; i++)ans1=ans1*i%md,ans2=ans2*i%md;
        for(int i=n-m=1; i<=n; i++)ans1=ans1*i%md;
        return ans1*fastpow(ans2,md-2,md)%md;
    }
    template<class T> ll C(int n,int m,T md=1e18) {
        return A(n,m,md)*fastpow(A(m,m,md),md-2,md)%md;
    }
    template<class T> ll myfloor(T n,T m) {
        return n%m==0 ? n/m : (n/m+1);
    }
}

using namespace math;

namespace graph {
    template<class T> void floyd(T *a,int n) {
        for(int k=1; k<=n; k++) {
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    a[i][j]=min(a[i][k]+a[k][j],a[i][j]);
                }
            }
        }
    }
}

int n,m,d;
struct edge {
    int to,next;
} e[N<<1];

int head[N],cnt;
int stk[N],tot=0;
int p[N],rhs=0,tim;
int dfn[N],low[N];
int vis[N],flag[N];
char S[N];
int pd=0;
int que[N];
int num[N][3];
char s[N][3];

void add(int u,int v) {
    e[++cnt]= {v,head[u]};
    head[u]=cnt;
}

int get(int k,char s) {
    if (S[k]=='a') {
        if (s=='B') return k;
        else return k+n;
    }
    if (S[k]=='b') {
        if (s=='A') return k;
        else return k+n;
    }
    if (S[k]=='c') {
        if (s=='A') return k;
        else return k+n;
    }
}

int fan(int x) {
    if (x>n) return x-n;
    else return x+n;
}

void tarjan(int x) {
    vis[x]=1;
    dfn[x]=low[x]=++tim;
    flag[x]=1;
    stk[++tot]=x;
    for(int i=head[x]; i; i=e[i].next) {
        int v=e[i].to;
        if(vis[v]) {
            if(flag[v]) low[x]=min(low[x],dfn[v]);
        } else {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
    }
    if(low[x]==dfn[x]) {
        rhs++;
        while(stk[tot]!=x) {
            flag[stk[tot]]=0;
            p[stk[tot]]=rhs;
            tot--;
        }
        flag[stk[tot]]=0;
        p[stk[tot]]=rhs;
        tot--;
    }
}

void clean() {
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(p,0,sizeof(p));
    memset(vis,0,sizeof(vis));
    memset(flag,0,sizeof(flag));
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    tim=0;tot=0;
    tot=0;cnt=0;
}

bool solve() {
    clean();
    int a,b;
    char ha,hb;
    for (int i=1; i<=m; i++) {
        a=num[i][1],b=num[i][2];
        ha=s[i][1],hb=s[i][2];
        if(S[a]==ha+32)continue ;
        int n1=get(a,ha);
        int n2=get(b,hb);
        if (S[b]==hb+32) {
            add(n1, fan(n1));
        } else {
            add(n1, n2);
            add(fan(n2), fan(n1));
        }
    }
    for (int i=1; i<=2*n; i++) {
        if (!vis[i]) tarjan(i);
    }
    for (int i=1; i<=n; i++) {
        if (p[i]==p[i+n]) return 0;
    }
    return 1;
}

void dfs(int k) {
    if (k>d) {
        if(solve()) pd=1;
        return ;
    }
    for (int i=0; i<2; i++) {
        S[que[k]]=i+'a';
        dfs(k+1);
        if(pd)return ;
    }
}

signed main() {
    read(n);
    read(d);
    d=0;
    for (int i=1; i<=n; i++) {
        S[i]=getchar();
        if (S[i]=='x') que[++d]=i;
    }
    read(m);
    for (int i=1; i<=m; i++) {
        scanf("%d %c %d %c",&num[i][1],&s[i][1],&num[i][2],&s[i][2]);
    }
    dfs(1);
    if (!pd) {
        puts("-1");
        return 0;
    }
    for (int i=1; i<=n; i++) {
        if (S[i]=='a') {
            if (p[i]<p[i+n]) putchar('B');
            else putchar('C');
        }
        if (S[i]=='b') {
            if (p[i]<p[i+n]) putchar('A');
            else putchar('C');
        }
        if (S[i]=='c') {
            if (p[i]<p[i+n]) putchar('A');
            else putchar('B');
        }
    }
    return 0;
}

Subtask2没过