题解

（请在此补充题目的中文题解与思路描述。）

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using tpl = tuple<int, int, int, int>;

const int N = 1e5 + 10;

int n, d, m, tp[N];
int dfn[N], low[N], stk[N], top, tot, cnt, scc[N];
bool f[N];
string s;
vector<int> pos, g[N];
vector<tpl> rule;

void tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u, f[u] = 1;
    for (int v : g[u]) {
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if (f[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        cnt++;
        while (1) {
            int k = stk[top--];
            scc[k] = cnt, f[k] = 0;
            if (u == k) break;
        }
    }
}

void Clear() {
    tot = cnt = top = 0;
    for (int i = 1; i <= 2 * n; i++) {
        dfn[i] = low[i] = scc[i] = stk[i] = f[i] = 0, g[i].clear();
    }
}

void dfs(int t) {
    if (t == pos.size()) {
        for (auto [i, a, j, b] : rule) {
            if (tp[i] != a && tp[j] != b) {
                int k1 = i, k2 = j;
                if (tp[i] == 1) k1 += (!a ? 0 : n);
                else k1 += (tp[i] ? a * n : (a - 1) * n);

                if (tp[j] == 1) k2 += (!b ? 0 : n);
                else k2 += (tp[j] ? b * n : (b - 1) * n);

                g[k1].push_back(k2);
                g[(k2 > n ? k2 - n : k2 + n)].push_back(k1 > n ? k1 - n : k1 + n);
                //cout << tp[i] << ' ' << tp[j] << ' ' << i << ' ' << a << ' ' << j << ' ' << b << ' ' << k1 << ' ' << k2 << '\n';
            } else if (tp[j] == b && tp[i] != a) {
                int k = i;
                if (tp[i] == 1) k += (!a ? 0 : n);
                else k += (tp[i] ? a * n : (a - 1) * n);
                g[k].push_back((k > n ? k - n : k + n));
            }
        }
        for (int i = 1; i <= n; i++) {
            if (dfn[i] == N && dfn[i + n] == N) {
                Clear(); return ;
            } else if (dfn[i] == N) tarjan(i + n);
            else if (dfn[i + n] == N) tarjan(i);
        }
        for (int i = 1; i <= 2 * n; i++) if (!dfn[i]) tarjan(i);
        for (int i = 1; i <= n; i++) {
            if (scc[i] == scc[i + n]) {
                Clear(); return ;
            }
        }
        for (int i = 1; i <= n; i++) {
            int ans = scc[i] > scc[i + n];
            //cout << scc[i] << ' ' << scc[i + n] << ' ';
            cout << char((!tp[i] ? ans + 1 : (tp[i] == 1 ? 2 * ans : ans)) + 'A');
        }
        exit(0);
    }
    tp[pos[t]] = 0, dfs(t + 1);
    tp[pos[t]] = 1, dfs(t + 1);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> d >> s;
    for (int i = 1; i <= n; i++) {
        tp[i] = (s[i - 1] == 'x' ? 3 : s[i - 1] - 'a');
        if (tp[i] == 3) pos.push_back(i);
    }
    cin >> m, rule.resize(m);
    for (auto &[i, a, j, b] : rule) {
        char x, y; cin >> i >> x >> j >> y;
        a = x - 'A', b = y - 'A';
    }
    dfs(0), cout << -1;
    return 0;
}