楼主卡了好久也没有卡过 uoj 的 test12 ……

经测试 在评论区的 hack 数据中光是 Tarjan(x) 函数就用了 1s 的时间

为此楼主将 Tarjan 利用手写栈实现 但是效果依然不理想（在没有随机化限制次数的情况下难以通过洛谷讨论区的 hack）

顺便测试了一下限制次数 发现顶级数据仅仅跑了 250 次 Tarjan 也会被卡 $\rm{TLE}$

所以想问一下是 Tarjan 本身常数就不支持跑很多遍还是楼主写丑了……/kk

#include <bits/stdc++.h>
// #pragma GCC optimize(3,"Ofast","inline","-funroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
typedef double db;
//#define int long long
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
#define poly vector<int>
#define Bt(a) bitset<a>
#define bc __builtin_popcount
#define pc putchar
#define ci const int&
#define Mem(a, b) memset(a, b, sizeof a)
const int mod = 1e9+7;
const db eps = 1e-10;
inline int Max(ci x, ci y) {return x > y ? x : y;}
inline int Min(ci x, ci y) {return x < y ? x : y;}
inline db Max(db x, db y) {return x - y > eps ? x : y;}
inline db Min(db x, db y) {return x - y < eps ? x : y;}
inline int Add(ci x, ci y, ci M = mod) {return (x + y) % M;}
inline int Mul(ci x, ci y, ci M = mod) {return 1ll * x * y % M;}
inline int Dec(ci x, ci y, ci M = mod) {return (x - y + M) % M;}
typedef pair<int, int> pii;
inline int Abs(int x) {return x < 0 ? -x : x;}
//char buf[1<<21],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char Obuf[105000],*O=Obuf;//Siz shoule be the size of Out File
int pst[30],ptop;
inline void Fprint(){fwrite(Obuf,1,O-Obuf,stdout);}
inline void Fwrite(int x){
  if(x==0){*O++='0';if(O-Obuf>100000)Fprint(),O=Obuf;return;}
  if(x<0)*O++='-',x=-x;ptop=0;
  while(x)pst[++ptop]=x%10,x/=10;
  while(ptop)*O++=pst[ptop--]+'0';
  if(O-Obuf>100000)Fprint(),O=Obuf;
}
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') w = -1;ch = getchar();}
    while (isdigit(ch)) {s = s * 10 + ch - '0';ch = getchar();}
    return s * w;
}
inline void write(int x) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)write(x / 10);
	pc(x % 10 + '0');
}
inline int qpow(int x, int y) {
    int res = 1;
    while (y) {if (y & 1)res = Mul(res, x);x = Mul(x, x);y >>= 1;}
    return res;
}
inline void cadd(int &x, int y) {x += y;}
inline void cmul(int &x, int y) {x *= y;}
inline void cmax(int &x, int y) {x = Max(x, y);}
inline void cmin(int &x, int y) {x = Min(x, y);}
const int N = 1e5 + 10;
namespace Refined_heart{
	struct E {
		int nxt, to; 
	} e[300010];
	int head[N], tot;
	inline void link(int x, int y) {
		e[++tot] = (E){head[x], y};
		head[x] = tot;
	}
	struct Limit {
		int op[2]; 
		char C[2];
		Limit(int i_ = 0, char hi_ = ' ', int j_ = 0, char hj_ = ' ') {
			op[0] = i_; op[1] = j_;
			C[0] = hi_; C[1] = hj_;
		}
	} lim[N];
	int n, m, d;
	int pos[10], pcnt;
	char str[N];
	namespace TARJAN {
		int low[N], dfn[N], st[N], scc, col[N], top, inst[N], dfstime;
		void clear() {
			for(int i = 1; i <= (n << 1); ++i) {col[i] = inst[i] = dfn[i] = low[i] = 0;}
			top = scc = dfstime = 0;
		}
		int S[N], Stop;
		void Tarjan(int x) {
			Stop = 0;
			S[++Stop] = x;
			while(Stop) {
				int x = S[Stop]; if(!dfn[x]) low[x] = dfn[x] = ++dfstime, inst[x] = 1, st[++top] = x;
				int nxt = e[head[x]].to;
				head[x] = e[head[x]].nxt;
				if(!nxt) {
					if(Stop > 1) low[S[Stop - 1]] = Min(low[S[Stop - 1]], low[x]);
					if(low[x] == dfn[x]) {
						int y = 0;
						++scc;
						while(top) {
							y = st[top]; top = top - 1;
							col[y] = scc; inst[y] = 0;
							if(x == y) break;
						}
					}
					--Stop;
				}
				else {
					if(dfn[nxt] && inst[nxt]) low[x] = Min(low[x], dfn[nxt]);
					else if(!dfn[nxt]) S[++Stop] = nxt;
				}
			}
		}
		void work() {
			clear();
			for(int i = 1; i <= (n << 1); ++i) if(!dfn[i]) Tarjan(i);
		}
	}
	using namespace TARJAN;
	inline void print(int ps, int op) {
		if(op == 0) {
			if(str[ps] == 'a') pc('B');
			else pc('A');
		}
		if(op == 1) {
			if(str[ps] == 'c') pc('B');
			else pc('C');
		}
	}
	inline int oppo(int x) {
		if(x > n) x -= n;
		else x += n;
		return x;
	}
	inline int getpos(int ps, char c) {
		if(c - 'A' == str[ps] - 'a') return -1;
		if(c == 'A') return ps;
		if(c == 'B' && str[ps] == 'a') return ps;
		return ps + n;
	}
	int ct = 0;
	void workk() {
		tot = 0;
		for(int i = 1; i <= (n << 1); ++i) head[i] = 0;
		for(int i = 1; i <= m; ++i) {
			int x = getpos(lim[i].op[0], lim[i].C[0]);
			int y = getpos(lim[i].op[1], lim[i].C[1]);
			if(x == -1) {
				continue;
			}
			if(y == -1) {
				link(x, oppo(x));
				continue;
			}
			link(x, y); 
			link(oppo(y), oppo(x));
		}
		clock_t st = clock();
		TARJAN :: work();
		clock_t ed = clock();
		ct += ed - st;
		int fg = 0;
		for(int i = 1; i <= n; ++i) {
			if(col[i] == col[i + n]) {
				fg = 1;
				break;
			}
		}
		if(fg) return ;
		for(int i = 1; i <= n; ++i) {
			if(col[i] < col[i + n]) print(i, 0);
			else print(i, 1);
		}
		cout << '\n';
		exit(0);
	}
	int g[1 << 10];
	void solve(){
		srand((time(0)) + 114514);
		n = read(); d = read();
		scanf("%s", str + 1);
		m = read();
		for(int i = 1; i <= m; ++i) {
			int x = read(); char cx; cin >> cx;
			int y = read(); char cy; cin >> cy;
			lim[i] = Limit(x, cx, y, cy);
		}
		for(int i = 1; i <= n; ++i) if(str[i] == 'x') pos[pcnt] = i, ++pcnt;
		if(d == 0) {
			workk();
			puts("-1");
			return ;
		}
		for(int i = 0; i < (1 << d); ++i) g[i] = i;
		for(int i = 1; i <= 50; ++i) random_shuffle(g, g + (1 << d));
		int c = 0;
		for(int i = 0; i < (1 << d); ++i) {
			clock_t st = clock();
			for(int j = 0; j < d; ++j) {
				if(g[i] >> j & 1) str[pos[j]] = 'a';
				else str[pos[j]] = 'c';
			}
			workk();
			clock_t ed = clock();
			cout << ed - st << '\n';
			c += ed - st;
		} 
		puts("-1");
		cout << "total = " << c << '\n';
		cout << "tarjan total = " << ct << '\n';
	}
}
signed main(){
	freopen("in.txt","r",stdin);
	Refined_heart::solve();
	return 0;
}