题意：
现在有\(a,b,c\)三种车，每个赛道可能会存在限制：\(a\)表示不能选择\(a\)类型的赛车，\(b,c\)同理；\(x\)表示该赛道不受限制，但\(x\)类型的个数$\(d\leq 8\)。
同时赛道之间还存在\(m\)条关系，每个关系用\((i\ h_i\ j\ h_j)\)表示，意味着若在第\(i\)个赛道选择\(h_i\)类的车，则必须在\(j\)赛道选择\(h_j\)类的车。
现在问是否存在一种合法安排赛车的方案，有则任意输出一种方案，没有则输出\(-1\)。
思路：
- \(x\)类赛道个数较少，我们先不考虑其存在，那么问题变为了一个存在一些限制条件的\(2-sat\)问题，我们先来解决这个问题。
- 对于合法的限制，直接连边即可；若\(i\)赛道不能有\(h_i\)，因为我们本来就不考虑\(h_i\)的存在（2-sat问题），那么我们直接无视当前的限制；若\(j\)赛道不能有\(h_j\)，此时表示不能选\(h_i\)，那么连边\(h_i\rightarrow h_i'\)即可。
- 然后考虑\(x\)类赛道，因为个数很少，所以我们可以直接\(3^d\)枚举选择哪些情况，复杂度变为\(O(3^dn)\)。
- 然后这里有个特别巧妙的想法，就是正难则反，我们考虑枚举不选哪个，那么\(x\)类赛道也变成了某类具体的赛道。首先问题处理上方便了许多，统一为\(2-sat\)问题；其次，复杂度将为\(2^d\)，因为假设我们当前不选\(a\)，那么可以选择\(b,c\)，不选\(b\)，那么可以选择\(a,c\)，这样可以覆盖所有的情况了。
所以通过\(2^d\)枚举，问题转换为了一个带限制\(2-sat\)问题。感觉还是挺巧妙的，上午有点累没好好想，可惜了QAQ
代码如下：
/*
* Author: heyuhhh
* Created Time: 2019/12/2 11:21:16
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5, M = 1e5 + 5;
int n, m, d;
char s[N], t[N];
int pos[N], tot;
char x[N];
struct Edge {
int i, j;
char pi, pj;
}e[M];
vector<int> G[N], rG[N], vs;
int used[N], bel[N];
void adde(int from, int to) {
G[from].push_back(to);
rG[to].push_back(from);
}
void dfs(int v) {
used[v] = true;
for(int u: G[v]) {
if(!used[u])
dfs(u);
}
vs.push_back(v);
}
void rdfs(int v, int k) {
used[v] = true;
bel[v] = k;
for(int u: rG[v])
if(!used[u])
rdfs(u, k);
}
int scc() {
memset(used, 0, sizeof(used));
vs.clear();
for(int v = 1; v <= 2 * n; ++v)
if(!used[v]) dfs(v);
memset(used, 0, sizeof(used));
int k = 0;
for(int i = (int) vs.size() - 1; i >= 0; --i)
if(!used[vs[i]]) rdfs(vs[i], k++);
return k;
}
void work() {
for(int i = 1; i <= 2 * n; i++) G[i].clear(), rG[i].clear();
for(int i = 1; i <= n; i++) {
if(t[i] == 'a') {
x[i] = 'b';
x[i + n] = 'c';
} else if(t[i] == 'b') {
x[i] = 'a';
x[i + n] = 'c';
} else {
x[i] = 'a';
x[i + n] = 'b';
}
}
for(int i = 1; i <= m; i++) {
int u = e[i].i, v = e[i].j;
char pi = e[i].pi, pj = e[i].pj;
if(t[u] == pi) continue;
if(t[v] == pj) {
if(x[u] == pi) adde(u, u + n);
else adde(u + n, u);
} else {
if(x[u] == pi) {
if(x[v] == pj) adde(u, v), adde(v + n, u + n);
else adde(u, v + n), adde(v, u + n);
} else {
if(x[v] == pj) adde(u + n, v), adde(v + n, u);
else adde(u + n, v + n), adde(v, u);
}
}
}
scc();
for(int i = 1; i <= n; i++) {
if(bel[i] == bel[i + n]) return;
}
for(int i = 1; i <= n; i++) {
if(bel[i] > bel[i + n]) {
printf("%c", x[i] - 'a' + 'A');
} else printf("%c", x[i + n] - 'a' + 'A');
}
cout << '\n';
exit(0);
}
void go(int cur) {
if(cur > tot) {
work(); return;
}
t[pos[cur]] = 'a'; go(cur + 1);
t[pos[cur]] = 'b'; go(cur + 1);
}
void run(){
scanf("%s", s + 1);
for(int i = 1; i <= n; i++) {
t[i] = s[i];
if(s[i] == 'x') pos[++tot] = i;
}
cin >> m;
for(int i = 1; i <= m; i++) {
int u, v;
char pi, pj;
scanf("%d %c %d %c", &u, &pi, &v, &pj);
pi = pi - 'A' + 'a';
pj = pj - 'A' + 'a';
e[i] = Edge {u, v, pi, pj};
}
go(1);
cout << -1 << '\n';
}
int main() {
while(cin >> n >> d) run();
return 0;
}