Problem:


Score : 900 points

Problem Statement

You are given an undirected graph consisting of N vertices and M edges.
The vertices are numbered 1 to N, and the edges are numbered 1 to M.
In addition, each vertex has a label, A or B. The label of Vertex i is s_i.
Edge i bidirectionally connects vertex a_i and b_i.

The phantom thief Nusook likes to choose some vertex as the startpoint and traverse an edge zero or more times.
Today, he will make a string after traveling as above, by placing the labels of the visited vertices in the order visited, beginning from the startpoint.

For example, in a graph where Vertex 1 has the label A and Vertex 2 has the label B, if Nusook travels along the path 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 2, the resulting string is ABABB.

Determine if Nusook can make all strings consisting of A and B.

Constraints

2 \leq N \leq 2 \times 10^{5}

1 \leq M \leq 2 \times 10^{5}

|s| = N

s_i is A or B.

1 \leq a_i, b_i \leq N

The given graph may NOT be simple or connected.

Input

Input is given from Standard Input in the following format:

N M
s
a_1 b_1
:
a_{M} b_{M}

Output

If Nusook can make all strings consisting of A and B, print Yes; otherwise, print No.

Sample Input 1

2 3
AB
1 1
1 2
2 2

Sample Output 1

Yes

Since Nusook can visit Vertex 1 and Vertex 2 in any way he likes, he can make all strings consisting of A and B.

Sample Input 2

4 3
ABAB
1 2
2 3
3 1

Sample Output 2

No

For example, Nusook cannot make BB.

The given graph may not be connected.

Sample Input 3

13 23
ABAAAABBBBAAB
7 1
10 6
1 11
2 10
2 8
2 11
11 12
8 3
7 12
11 2
13 13
11 9
4 1
9 7
9 6
8 13
8 6
4 10
8 7
4 3
2 1
8 12
6 9

Sample Output 3

Yes

Sample Input 4

13 17
BBABBBAABABBA
7 1
7 9
11 12
3 9
11 9
2 1
11 5
12 11
10 8
1 11
1 8
7 7
9 10
8 8
8 12
6 2
13 11

Sample Output 4

No



Sample input:
2 3
AB
1 1
1 2
2 2


Sample output:
Yes

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

aa = [set() for i in range(N)]
bb = [set() for i in range(N)]
ab = [set() for i in range(N)]
ba = [set() for i in range(N)]

for x,y in src:
    if S[x] != S[y]:
        if S[x] == 'A':
            ab[x].add(y)
            ba[y].add(x)
        else:
            ba[x].add(y)
            ab[y].add(x)
    elif S[x] == 'A':
        aa[x].add(y)
        aa[y].add(x)
    else:
        bb[x].add(y)
        bb[y].add(x)


skip = [False] * N
def remove(i):
    if skip[i]: return
    if S[i] == 'A':
        if aa[i]: return
        for b in ab[i]:
            if i in ba[b]:
                ba[b].remove(i)
            remove(b)
        ab[i] = set()
    else:
        if bb[i]: return
        for a in ba[i]:
            if i in ab[a]:
                ab[a].remove(i)
            remove(a)
        ba[i] = set()
    skip[i] = True

for i in range(N):
    remove(i)


mem = [[None]*N for i in range(4)]
def rec(v, depth):
    if mem[depth][v] is not None:
        return mem[depth][v]
    ret = False
    if depth == 0:
        for to in ab[v]:
            if rec(to, depth+1):
                ret = True
                break
    elif depth == 1:
        for to in bb[v]:
            if rec(to, depth+1):
                ret = True
                break
    elif depth == 2:
        for to in ba[v]:
            if rec(to, depth+1):
                ret = True
                break
    else:
        for to in aa[v]:
            if ab[to]:
                ret = True
    mem[depth][v] = ret
    return ret

for i in range(N):
    if rec(i, 0):
        print('Yes')
        exit()

print('No')

Submission status: Wrong Answer

Solution code:
import sys

n, m = map(int, input().split())
s = input()
es = []
bb = [set() for _ in range(n)]
ab = [set() for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	if s[a-1] == "A":
		if s[b-1] == "A":
			es.append([a-1, b-1])
		else:
			ab[a-1].add(b-1)
	if s[a-1] == "B":
		if s[b-1] == "B":
			bb[a-1].add(b-1)
			bb[b-1].add(a-1)
		else:
			ab[b-1].add(a-1)

#print(es, bb, ab, sep="\n")
for e in es:
	for p in ab[e[0]]:
		if ab[e[1]] & bb[p]:
			print("Yes")
			sys.exit()
for e in es:
	for p in ab[e[1]]:
		if ab[e[0]] & bb[p]:
			print("Yes")
			sys.exit()



print("No")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
S=input()
G=[set() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].add(b-1)
    G[b-1].add(a-1)
H=[set() for i in range(N)]
for i in range(N):
    for p in G[i]:
        H[i].add(S[p])
D=dict()
X=[]
K=0
for i in range(N):
    if len(H[i])==2:
        X.append(i)
        D[i]=K
        K+=1
A=[set() for i in range(K)]
T=""
for i in range(N):
    if i in D:
        k=D[i]
        for p in G[i]:
            if p in D:
                A[k].add(D[p])
for i in range(K):
    T+=S[X[i]]
B=[set() for i in range(K)]
for i in range(K):
    for p in A[i]:
        B[i].add(T[p])
for i in range(K):
    if len(B[i])==1:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
# C
from collections import deque

N, M = map(int, input().split())
s = list(input())
s_ = []
for c in s:
    s_.append(c)

# Graph
G = dict()
for i in range(1, N+1):
    G[i] = dict()

for _ in range(M):
    a, b = map(int, input().split())
    G[a][b] = 1
    G[b][a] = 1
    
# clean up
queue = deque()
go = True

As = [0]*N
Bs = [0]*N

for i in range(1, N+1):
    if s[i-1] != "C":
        a = 0
        b = 0
        for k in G[i].keys():
            v = s[k-1]
            if v == "A":
                a += 1
            elif v == "B":
                b += 1
        As[i-1] = a
        Bs[i-1] = b
        if a*b == 0:
            queue.append(i)
            s[i-1] = "C"

while len(queue) > 0:
    j = queue.popleft()
    for i in G[j].keys():
        if s[i-1] != "C":
            if s_[j-1] == "A":
                As[i-1] -= 1
            else:
                Bs[i-1] -= 1
            if As[i-1] * Bs[i-1] == 0:
                queue.append(i)
                s[i-1] = "C"

if "A" in s and "B" in s:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
S=input()
G=[set() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].add(b-1)
    G[b-1].add(a-1)
H=[set() for i in range(N)]
for i in range(N):
    for p in G[i]:
        H[i].add(S[p])
D=dict()
X=[]
K=0
for i in range(N):
    if len(H[i])==2:
        X.append(i)
        D[i]=K
        K+=1
A=[set() for i in range(K)]
T=""
for i in range(N):
    if i in D:
        k=D[i]
        for p in G[i]:
            if p in D:
                A[k].add(D[p])
for i in range(K):
    T+=S[X[i]]
B=[set() for i in range(K)]
for i in range(K):
    for p in A[i]:
        B[i].add(T[p])
for i in range(K):
    if len(B[i])!=2:
        print("No")
        exit()
print("Yes")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab_str = input()

arr = []
for i in range(0, m):
    arr.append(list(map(int, input().split())))

arr2 = []
for a in arr:
    arr2.append(list((ab_str[a[0]-1], ab_str[a[1]-1])))

# print(arr2)

a = 0;
b = 0;
for test in arr2:
    if b == 0:
        if test == ['B', 'B']:
            b = 1
    if a == 0:
        if test == ['A', 'A']:
            a = 1

if a == 1 and b == 1:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys

n, m = map(int, input().split())
s = input()
es = []
bb = [set() for _ in range(n)]
ab = [set() for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	if s[a-1] == "A":
		if s[b-1] == "A":
			es.append([a-1, b-1])
		else:
			ab[a-1].add(b-1)
	if s[a-1] == "B":
		if s[b-1] == "B":
			bb[a-1].add(b-1)
			bb[b-1].add(a-1)
		else:
			ab[b-1].add(a-1)

#print(es, bb, ab, sep="\n")
for e in es:
	for p in ab[e[0]]:
		if ab[e[1]] & bb[p]:
			print("Yes")
			sys.exit()

print("No")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
listS = list(input())
index =0
flagAA =0
flagBB =0
flagAB =0
listAA =[]
listAA1 =[]
listAA2 =[]
listBB =[]
listBB1 =[]
listBB2 =[]
listAB =[]
listAB1 =[]
listAB2 =[]
while index<m:
    index+=1
    a, b = map(int, input().split())
    if listS[a-1] == "A" and listS[b-1] == "A":
        flagAA =1
        listAA.append([a-1, b-1])
        listAA1.append(a-1)
        listAA2.append(b-1)
    elif listS[a-1] == "B" and listS[b-1] == "B":
        flagBB =1
        listBB.append([a-1, b-1])
        listBB1.append(a-1)
        listBB2.append(b-1)
    else:
        flagAB =1
        if listS[a-1] == "A" and listS[b-1] == "B":
            listAB.append([a-1, b-1])
            listAB1.append(a-1)
            listAB2.append(b-1)
        else:
            listAB.append([b-1, a-1])
            listAB1.append(b-1)
            listAB2.append(a-1)

if flagAA == 1 and flagAB ==1 and flagBB ==1:
        listAB.sort()
        listAA1.sort()
        listBB1.sort()
        listAA2.sort()
        listBB2.sort()
        index =0
        index2 =0
        index3 =0
        flag=0
        while index < len(listAB):
            if listAB[index][0] in listAA1:
                if listAB[index][1] in listBB1:
                    if listAA[listAA1.index(listAB[index][0])][0] == listAA[listAA1.index(listAB[index][0])][1]:
                        if listBB[listBB1.index(listAB[index][1])][0] == listBB[listBB1.index(listAB[index][1])][1]:
                            print("Yes")
                            flag =1
                            break
                        else:
                            if listBB[listBB1.index(listAB[index][1])][0] != listAB[index][1] and listBB[listBB1.index(listAB[index][1])][0] in listAB2:
                                target = listBB[listBB1.index(listAB[index][1])][0]
                                if listAB[listAB2.index(target)][0] in listAA1 or listAA2:
                                    print("Yes")
                                flag =1
                                break
                            elif listBB[listBB1.index(listAB[index][1])][1] != listAB[index][1] and listBB[listBB1.index(listAB[index][1])][1] in listAB2:
                                target = listBB[listBB1.index(listAB[index][1])][1]
                                if listAB[listAB2.index(target)][0] in listAA1 or listAA2:
                                    print("Yes")
                                flag =1
                                break
                    elif listBB[listBB1.index(listAB[index][1])][0] == listBB[listBB1.index(listAB[index][1])][1]:
                        if listAA[listAA1.index(listAB[index][0])][0] != listAB[index][0] and listAA[listAA1.index(listAB[index][0])][0] in listAB1:
                            target = listAA[listAA1.index(listAB[index][0])][0]
                            if listAB[listAB1.index(target)][1] in listBB1 or listBB2:
                                print("Yes")
                            flag =1
                            break
                        elif listAA[listAA1.index(listAB[index][0])][1] != listAB[index][0] and listAA[listAA1.index(listAB[index][0])][1] in listAB1:
                            target = listAA[listAA1.index(listAB[index][0])][1]
                            if listAB[listAB1.index(target)][1] in listBB1 or listBB2:
                                print("Yes")
                            flag =1
                            break
                    
            elif listAB[index][0] in listAA2:
                if listAB[index][1] in listBB1:
                    if listAA[listAA2.index(listAB[index][0])][0] == listAA[listAA2.index(listAB[index][0])][1]:
                        if listBB[listBB1.index(listAB[index][1])][0] == listBB[listBB1.index(listAB[index][1])][1]:
                            print("Yes")
                            flag =1
                            break
                        else:
                            if listBB[listBB1.index(listAB[index][1])][0] != listAB[index][1] and listBB[listBB1.index(listAB[index][1])][0] in listAB2:
                                target = listBB[listBB1.index(listAB[index][1])][0]
                                if listAB2.index(target) in listAA1 or listAA2:
                                    print("Yes")
                                flag =1
                                break
                            elif listBB[listBB1.index(listAB[index][1])][1] != listAB[index][1] and listBB[listBB1.index(listAB[index][1])][1] in listAB2:
                                target = listBB[listBB1.index(listAB[index][1])][1]
                                if listAB2.index(target) in listAA1 or listAA2:
                                    print("Yes")
                                flag =1
                                break
                    elif listBB[listBB1.index(listAB[index][1])][0] == listBB[listBB1.index(listAB[index][1])][1]:
                        if listAA[listAA2.index(listAB[index][0])][0] != listAB[index][0] and listAA[listAA2.index(listAB[index][0])][0] in listAB1:
                            target = listAA[listAA2.index(listAB[index][0])][0]
                            if listAB[listAB1.index(target)][1] in listBB1 or listBB2:
                                print("Yes")
                            flag =1
                            break
                        elif listAA[listAA2.index(listAB[index][0])][1] != listAB[index][0] and listAA[listAA2.index(listAB[index][0])][1] in listAB1:
                            target = listAA[listAA2.index(listAB[index][0])][1]
                            if listAB[listAB1.index(target)][1] in listBB1 or listBB2:
                                print("Yes")
                            flag =1
                            break
            elif listAB[index][0] in listAA1:
                if listAB[index][1] in listBB2:
                    if listAA[listAA1.index(listAB[index][0])][0] == listAA[listAA1.index(listAB[index][0])][1]:
                        if listBB[listBB2.index(listAB[index][1])][0] == listBB[listBB2.index(listAB[index][1])][1]:
                            print("Yes")
                            flag =1
                            break
                        else:
                            if listBB[listBB2.index(listAB[index][1])][0] != listAB[index][1] and listBB[listBB1.index(listAB[index][1])][0] in listAB2:
                                target = listBB[listBB2.index(listAB[index][1])][0]
                                if listAB2.index(target) in listAA1 or listAA2:
                                    print("Yes")
                                flag =1
                                break
                            elif listBB[listBB2.index(listAB[index][1])][1] != listAB[index][1] and listBB[listBB1.index(listAB[index][1])][1] in listAB2:
                                target = listBB[listBB2.index(listAB[index][1])][1]
                                if listAB2.index(target) in listAA1 or listAA2:
                                    print("Yes")
                                flag =1
                                break
                    elif listBB[listBB2.index(listAB[index][1])][0] == listBB[listBB2.index(listAB[index][1])][1]:
                        if listAA[listAA1.index(listAB[index][0])][0] != listAB[index][0] and listAA[listAA1.index(listAB[index][0])][0] in listAB1:
                            target = listAA[listAA1.index(listAB[index][0])][0]
                            if listAB[listAB1.index(target)][1] in listBB2 or listBB2:
                                print("Yes")
                            flag =1
                            break
                        elif listAA[listAA1.index(listAB[index][0])][1] != listAB[index][0] and listAA[listAA1.index(listAB[index][0])][1] in listAB1:
                            target = listAA[listAA1.index(listAB[index][0])][1]
                            if listAB[listAB1.index(target)][1] in listBB2 or listBB2:
                                print("Yes")
                            flag =1
                            break
            elif listAB[index][0] in listAA2:
                if listAB[index][1] in listBB2:
                    if listAA[listAA2.index(listAB[index][0])][0] == listAA[listAA2.index(listAB[index][0])][1]:
                        if listBB[listBB2.index(listAB[index][1])][0] == listBB[listBB2.index(listAB[index][1])][1]:
                            print("Yes")
                            flag =1
                            break
                        else:
                            if listBB[listBB2.index(listAB[index][1])][0] != listAB[index][1] and listBB[listBB1.index(listAB[index][1])][0] in listAB2:
                                target = listBB[listBB2.index(listAB[index][1])][0]
                                if listAB2.index(target) in listAA1 or listAA2:
                                    print("Yes")
                                flag =1
                                break
                            elif listBB[listBB2.index(listAB[index][1])][1] != listAB[index][1] and listBB[listBB1.index(listAB[index][1])][1] in listAB2:
                                target = listBB[listBB2.index(listAB[index][1])][1]
                                if listAB2.index(target) in listAA1 or listAA2:
                                    print("Yes")
                                flag =1
                                break
                    elif listBB[listBB2.index(listAB[index][1])][0] == listBB[listBB2.index(listAB[index][1])][1]:
                        if listAA[listAA2.index(listAB[index][0])][0] != listAB[index][0] and listAA[listAA2.index(listAB[index][0])][0] in listAB1:
                            target = listAA[listAA2.index(listAB[index][0])][0]
                            if listAB[listAB1.index(target)][1] in listBB2 or listBB2:
                                print("Yes")
                            flag =1
                            break
                        elif listAA[listAA2.index(listAB[index][0])][1] != listAB[index][0] and listAA[listAA2.index(listAB[index][0])][1] in listAB1:
                            target = listAA[listAA2.index(listAB[index][0])][1]
                            if listAB[listAB1.index(target)][1] in listBB2 or listBB2:
                                print("Yes")
                            flag =1
                            break
            index+=1
            if index == len(listAB):
                print("No")            
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

aa = [set() for i in range(N)]
bb = [set() for i in range(N)]
ab = [set() for i in range(N)]
ba = [set() for i in range(N)]

for x,y in src:
    if S[x] != S[y]:
        if S[x] == 'A':
            ab[x].add(y)
            ba[y].add(x)
        else:
            ba[x].add(y)
            ab[y].add(x)
    elif S[x] == 'A':
        aa[x].add(y)
        aa[y].add(x)
    else:
        bb[x].add(y)
        bb[y].add(x)

for i,c in enumerate(S):
    if c == 'A':
        if aa[i]: continue
        for b in ab[i]:
            if i in ba[b]:
                ba[b].remove(i)
        ab[i] = set()
    else:
        if bb[i]: continue
        for a in ba[i]:
            if i in ab[a]:
                ab[a].remove(i)
        ba[i] = set()

mem = [[None]*N for i in range(4)]
def rec(v, depth):
    if mem[depth][v] is not None:
        return mem[depth][v]
    ret = False
    if depth == 0:
        for to in ab[v]:
            if rec(to, depth+1):
                ret = True
                break
    elif depth == 1:
        for to in bb[v]:
            if rec(to, depth+1):
                ret = True
                break
    elif depth == 2:
        for to in ba[v]:
            if rec(to, depth+1):
                ret = True
                break
    else:
        for to in aa[v]:
            if ab[to]:
                ret = True
    mem[depth][v] = ret
    return ret

for i in range(N):
    if rec(i, 0):
        print('Yes')
        exit()

print('No')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

aa = [set() for i in range(N)]
bb = [set() for i in range(N)]
ab = [set() for i in range(N)]
ba = [set() for i in range(N)]

for x,y in src:
    if S[x] != S[y]:
        if S[x] == 'A':
            ab[x].add(y)
            ba[y].add(x)
        else:
            ba[x].add(y)
            ab[y].add(x)
    elif S[x] == 'A':
        aa[x].add(y)
        aa[y].add(x)
    else:
        bb[x].add(y)
        bb[y].add(x)

for i,c in enumerate(S):
    if c == 'A':
        if aa[i]: continue
        for b in ab[i]:
            if i in ba[b]:
                ba[b].remove(i)
        ab[i] = set()
    else:
        if bb[i]: continue
        for a in ba[i]:
            if i in ab[a]:
                ab[a].remove(i)
        ba[i] = set()

# print(aa)
# print(bb)
# print(ab)
# print(ba)

mem = [[None]*N for i in range(4)]
def rec(v, depth):
    if mem[depth][v] is not None:
        return mem[depth][v]
    ret = False
    if depth == 0:
        for to in ab[v]:
            if rec(to, depth+1):
                ret = True
                break
    elif depth == 1:
        for to in bb[v]:
            if rec(to, depth+1):
                ret = True
                break
    elif depth == 2:
        for to in ba[v]:
            if rec(to, depth+1):
                ret = True
                break
    else:
        if aa[v]: ret = True
    mem[depth][v] = ret
    return ret

for i in range(N):
    if rec(i, 0):
        print('Yes')
        exit()

print('No')

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ab = input()
nodes = []
for i in range(M):
    nodes.append(list(map(int, input().split())))

def judge(N, M, ab, nodes):
    for i in range(N):
        judger = set()
        for node in nodes:
            if node[0] == i + 1:
                if ab[node[1] - 1] == 'A':
                    judger.add('A')
                if ab[node[1] - 1] == 'B':
                    judger.add('B')
        for node in nodes :
            if node[1] == i + 1:
                if ab[node[0] - 1] == 'A':
                    judger.add('A')
                if ab[node[0] - 1] == 'B':
                    judger.add('B')
        if len(judger) != 2:
            return 'No'
    return 'Yes'
print(judge(N, M, ab, nodes))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ab = input()
nodes = []
for i in range(M):
    nodes.append(list(map(int, input().split())))
def judge(N, M, ab, nodes):
    for i in range(N):
        judger = set()
        for node in nodes:
            if node[0] == i + 1:
                if ab[node[1] - 1] == 'A':
                    judger.add('A')
                if ab[node[1] - 1] == 'B':
                    judger.add('B')
        print(judger)
        for node in nodes :
            if node[1] == i + 1:
                if ab[node[0] - 1] == 'A':
                    judger.add('A')
                if ab[node[0] - 1] == 'B':
                    judger.add('B')
        print(judger)
        if len(judger) != 2:
            return 'No'
    return 'Yes'
print(judge(N, M, ab, nodes))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = [str(x) for x in input()]
a = {}
aa = []
bb = []
ab = []
for _ in range(m):
	l, r = map(int, input().split())
	if s[l-1]+s[r-1] == 'AA':
		aa.append([str(l), str(r)])
	elif s[l-1]+s[r-1] in ['AB', 'BA']:
		ab.append([str(l), str(r)])
	elif s[l-1]+s[r-1] == 'BB':
		bb.append([str(l), str(r)])
	a.setdefault(''.join([str(l),str(r)]),s[l-1]+s[r-1] )
ans = 'No'
for i in aa:
	if i[0] != '1':
		break
	for j in ab:
		for k in bb:
			if i[1] == j[0] and j[1] == k[0]:
				ans = 'Yes'	
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


# --------------------------------------------

dp = None

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

def main():
    N, M = li_input()
    S = "X" + input()
    V = [i for i in range(1, N+1)]
    E = [li_input() for _ in range(M)]
    R = [False for _ in range(N+1)]

    D = collections.defaultdict(lambda: [])

    for e in E:
        D[e[0]].append(e[1])
        D[e[1]].append(e[0])

    for k in D.keys():
        D[k].sort()

    clusters = []

    for v in V:
        # 到達済みならスルー
        if R[v]:
            continue

        # 到達済みにする
        R[v] = True

        cluster = [v]
        next_v_list = D[v]

        # 幅優先探索
        while len(next_v_list) != 0:
            for next_v in next_v_list:
                new_next_v_list = []

                # 到達済みならスルー
                if R[next_v]:
                    continue

                # 到達済みにする
                R[next_v] = True

                # クラスタに加える
                cluster.append(next_v)

                new_next_v_list.extend(D[next_v])
            
            next_v_list = new_next_v_list

        clusters.append(cluster)

    # print(clusters)

    # Vectorが1なら絶対ダメなので削除
    clusters_multiple = []
    for cluster in clusters:
        if len(cluster) != 1:
            clusters_multiple.append(cluster)

    # print(clusters_multiple)

    clusters_AB = []
    # クラスタ内にAB両方が含まれていなければダメなので削除
    for cluster in clusters_multiple:
        cluster_AB = []

        for vector in cluster:
            cluster_AB.append(S[vector])

        if len(set(cluster_AB)) == 2:
            clusters_AB.append(cluster)
        
    # 要素数順にソート
    clusters_AB.sort(key=lambda l:len(l))
    
    # print(clusters_AB)

    for cluster in clusters_AB:
        # クラスタに属するVが2なら
        # 各々の自己参照と2つをつなぐEがいる
        if len(cluster) == 2:
            loop1 = bisearch(D[cluster[0]], cluster[0])
            loop2 = bisearch(D[cluster[1]], cluster[1])
            connect = bisearch(D[cluster[1]], cluster[0])

            if loop1 and loop2 and connect:
                print("Yes")
                return

        # クラスタに属するVが3なら
        # 任意の2つのVの組み合わせにおいて
        # 各々の自己参照と2つをつなぐEとABがいる
        elif len(cluster) == 3:
            for i in range(2):
                for j in range(i + 1, 3):
                    loop1 = bisearch(D[cluster[i]], cluster[i])
                    loop2 = bisearch(D[cluster[j]], cluster[j])
                    connect = bisearch(D[cluster[i]], cluster[j])
                    containAB = S[cluster[i]] != S[cluster[j]]

                    if loop1 and loop2 and connect and containAB:
                        print("Yes")
                        return

        # クラスタに属するVが4以上なら
        else:
            cluster_A = []
            cluster_B = []
            for vector in cluster:
                if S[vector] == "A":
                    cluster_A.append(vector)
                else:
                    cluster_B.append(vector)

            # print(cluster_A, cluster_B)

            # まず，ABとなる任意の2つのVの組み合わせにおいて，
            # 各々の自己参照と2つをつなぐEがいる
            for ia in range(len(cluster_A)):
                for ib in range(len(cluster_B)):
                    loop1 = bisearch(D[cluster_A[ia]], cluster_A[ia])
                    loop2 = bisearch(D[cluster_B[ib]], cluster_B[ib])
                    connect = bisearch(D[cluster_B[ib]], cluster_A[ia])

                    if loop1 and loop2 and connect:
                        print("Yes")
                        return

            # 次に，AABBとなる任意の4つのVの組み合わせにおいて
            # A - B
            # |   |
            # A - B
            # となる部分グラフがあれば成立
            for ia in range(len(cluster_A) - 1):
                for ja in range(ia + 1, len(cluster_A)):
                    for ib in range(len(cluster_B) - 1):
                        for jb in range(ib + 1, len(cluster_B)):
                            connect_aa = bisearch(D[cluster_A[ja]], cluster_A[ia])
                            connect_bb = bisearch(D[cluster_B[jb]], cluster_B[ib])
                            connect_ab1 = bisearch(D[cluster_B[ib]], cluster_A[ia]) and bisearch(D[cluster_B[jb]], cluster_A[ja])
                            connect_ab2 = bisearch(D[cluster_B[jb]], cluster_A[ia]) and bisearch(D[cluster_B[ib]], cluster_A[ja])

                            if connect_aa and connect_bb and (connect_ab1 or connect_ab2):
                                print("Yes")
                                return
    
    print("No")



                


main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
s = input()
a = []
b = []
A_path = 0
B_path = 0
for i in range(M):
    tmpa, tmpb = map(int, input().split())
    a.append(tmpa)
    b.append(tmpb)

for i in range(M):
    if s[a[i]-1] == s[b[i]-1]:
        if s[a[i]-1] == "A":
            A_path = 1
        elif s[a[i]-1] == "B":
            B_path = 1

if A_path == 1 and B_path == 1:
    print("Yes")
else:
    print("No")