Language: C++

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int MAX = 200000;
struct Edge {
	vector<int> nodeA;
	vector<int> nodeB;
};

vector<int> getPair(int x, vector<pair<int, int> > pair) {
	int min = 0, max = pair.size();
	for (int mid = max >> 1;max - min > 1;mid = min + (max - min >> 1)) {
		if (pair[mid].first < x) min = mid;
		else max = mid;
	}
	vector<int> ret;
	for (;min < pair.size() && pair[min].first <= x;++ min) {
		if (pair[min].first == x) ret.push_back(pair[min].second);
	}
	return ret;
}

bool getPair(int x, vector<int> pair) {
	int min = 0, max = pair.size();
	for (int mid = max >> 1;max - min > 1;mid = min + (max - min >> 1)) {
		if (pair[mid] < x) min = mid;
		else max = mid;
	}
	return (min < pair.size() && pair[min] == x) || (max < pair.size() && pair[max] == x);
}

bool check(vector<pair<int, int> > pair, bool isA, Edge *e, bool *loop, int N) {
	for (int i = 0;i < pair.size();i ++) {
		vector<int> ch = isA ? e[pair[i].first].nodeB : e[pair[i].first].nodeA;
		int count = 0;
		for (int j = 0;j < ch.size();++ j) {
			if (loop[ch[j]]) {
				count ++;
				break;
			}
		}
		ch = isA ? e[pair[i].second].nodeB : e[pair[i].second].nodeA;
		for (int j = 0;j < ch.size();++ j) {
			if (loop[ch[j]]) {
				count ++;
				break;
			}
		}
		if (count >= 2) return true;
	}
	return false;
}

int main() {
	int N, M, a, b;
	string s;
	cin >> N >> M >> s;
	static Edge edge[MAX];
	static vector<pair<int, int> > Apair, Bpair; // A-AとB-Bの辺
	static bool loop[MAX];
	memset(loop, false, N);
	for (int i = 0;i < M;++ i) {
		cin >> a >> b;
		-- a; -- b;
		if (s[b] == 'A') edge[a].nodeA.push_back(b);
		else  edge[a].nodeB.push_back(b);
		if (s[a] == 'A') edge[b].nodeA.push_back(a);
		else edge[b].nodeB.push_back(a);
		if (s[a] == s[b]) {
			if (s[a] == 'A') {
				Apair.push_back(make_pair(a, b));
				Apair.push_back(make_pair(b, a));
			} else {
				Bpair.push_back(make_pair(a, b));
				Bpair.push_back(make_pair(b, a));
			}
		}
		if (a == b) loop[a] = true;
	}
	for (int i = 0;i < N;++ i) {
		sort(edge[i].nodeA.begin(), edge[i].nodeA.end());
		sort(edge[i].nodeB.begin(), edge[i].nodeB.end());
	}
	sort(Apair.begin(), Apair.end());
	sort(Bpair.begin(), Bpair.end());
	
/*	for (int i = 0;i < Apair.size();++ i) {
		cerr << "A:" << Apair[i].first << "," << Apair[i].second << endl;
	}
	for (int i = 0;i < Bpair.size();++ i) {
		cerr << "B:" << Bpair[i].first << "," << Bpair[i].second << endl;
	}*/
	
	for (int i = 0;i < Apair.size();++ i) {
		int a1 = Apair[i].first, a2 = Apair[i].second;
		for (int j = 0;j < edge[a1].nodeB.size();++ j) {
			static vector<int> b2 = getPair(edge[a1].nodeB[j], Bpair);
			for (int k = 0;k < b2.size();++ k) {
				if (getPair(b2[k], edge[a2].nodeB)) {
//					cerr << a1 << "," << a2 << " - " << edge[a1].nodeB[j] << "," << b2[k] << endl;
					cout << "Yes";
					return 0;
				}
			}
		}
	}
	if (check(Apair, true, edge, loop, N) || check(Bpair, false, edge, loop, N)) cout << "Yes";
	else cout << "No";
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

大事なことは、要素が2個しかないということ
つまり、A→Aの閉路、B→Bの閉路、A→B……の閉路の3個が存在してそれが隣接してればおk
これは、次のどれかを内包しているに他ならない
1. [1]=A, [2]=Bとして[1]-[1], [2]-[2], [1]-[2]
2. [1]=A, [2]=A, [3]=Bとして[1]-[2], [1]-[3], [2]-[3], [3]-[3]
3. [1]=A, [2]=B, [3]=Bとして[1]-[2], [1]-[3], [2]-[3], [1]-[1]
4. [1]=A, [2]=A, [3]=B, [4]=Bとして[1]-[2], [2]-[3], [3]-[4], [4]-[1]

まず、A-AとB-Bのペアを作っておく O(N)
そして、1個のAを決め打つ O(N)
この時、A-BとなるBを1個取り出し(O(logN))、そのペアとなるB(O(logN))とペアとなるA(O(log N))が自身のペアと一致するならYes
そうでないならNo
*/

Compiler output:
a.cc: In function 'int main()':
a.cc:63:9: error: 'memset' was not declared in this scope
   63 |         memset(loop, false, N);
      |         ^~~~~~
a.cc:4:1: note: 'memset' is defined in header '<cstring>'; this is probably fixable by adding '#include <cstring>'
    3 | #include<vector>
  +++ |+#include <cstring>
    4 | using namespace std;