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

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
n,m=map(int,input().split())
s=input()
A=[0]*n
B=[0]*n
Edges=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if a==b:
        if s[a]=='A':
            A[a]+=1
        else:
            B[a]+=1
    else:
        Edges[a].append(b)
        Edges[b].append(a)
        if s[a]=='A':
            A[b]+=1
        else:
            B[b]+=1
        if s[b]=='A':
            A[a]+=1
        else:
            B[a]+=1
Del=[False]*n
q=deque()
for i in range(n):
    if A[i]*B[i]==0:
        q.append(i)
        Del[i]=True
while q:
    u=q.pop()
    l=s[u]
    for v in Edges[u]:
        if Del[v]:
            continue
        if l=='A':
            A[v]-=1
        else:
            B[v]-=1
        if A[v]*B[v]==0:
            q.append(v)
            Del[v]=True
print('No' if sum(Del)==n else 'Yes')

Solution (Python):
from collections import deque
N,M=map(int,input().split())
s=input()
H=[[] for i in range(N)]
G=[[] for i in range(2*N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    H[a].append(b)
    H[b].append(a)
    if s[a]=="A":
        if s[b]=="A":
            G[a].append(N+b)
            G[b].append(N+a)
        else:
            G[a+N].append(b+N)
            G[b].append(a)
    else:
        if s[b]=="A":
            G[a].append(b)
            G[N+b].append(N+a)
        else:
            G[N+a].append(b)
            G[N+b].append(a)
K=[0 for i in range(2*N)]
for i in range(2*N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(2*N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
if len(res)==2*N:
    print("No")
else:
    print("Yes")

Solution (Python):
import sys
from collections import deque
N,M=map(int,input().split())
s=input()
table=[]
for i in range(M):
    x,y=map(int,input().split())
    table.append((x-1,y-1))
A=[0]*N
B=[0]*N
edge=[[] for i in range(N)]
S=[False]*N
L=deque()
for x,y in table:
    if x==y:
        
        if s[x]=='A':
            A[x]+=1
        else:
            B[x]+=1
        continue
    edge[x].append(y)
    edge[y].append(x)
    if s[x]=='A':
        A[y]+=1
    else:
        B[y]+=1
    if s[y]=='A':
        A[x]+=1
    else:
        B[x]+=1 
        
for i in range(N):
    if A[i]*B[i]==0:
        L.append(i)
        S[i]=True

while L:
    x=L.pop()
    t=s[x]
    for y in edge[x]:
        if S[y]:
            continue
        if t=='A':
            A[y]-=1
        else:
            B[y]-=1
        if A[y]*B[y]==0:
            L.append(y)
            S[y]=True
if sum(S)!=N:
    print('Yes')
else:
    print('No')

Solution (Python):
import sys
from collections import deque
N,M=map(int,input().split())
s=input()
table=[]
for i in range(M):
    x,y=map(int,input().split())
    table.append((x-1,y-1))
edge=[[]for i in range(2*N)]
visit=[0]*(2*N)
for x,y in table:
    if x==y:
        edge[2*x].append(2*x+1)
        visit[2*x+1]+=1
        continue
    if s[x]==s[y]:
        edge[2*x].append(2*y+1)
        edge[2*y].append(2*x+1)
        visit[2*x+1]+=1
        visit[2*y+1]+=1
        continue
    edge[2*x+1].append(2*y)
    edge[2*y+1].append(2*x)
    visit[2*x]+=1
    visit[2*y]+=1
S=set()
L=deque()

for i in range(2*N):
    if visit[i]==0:
        L.append(i)

while L:
    x=L.pop()
    S.add(x)
    for y in edge[x]:
        visit[y]-=1
        if visit[y]==0:
            L.append(y)
if len(S)!=2*N:
    print('Yes')
else:
    print('No')

Solution (Python):
import sys
from collections import deque
N,M=map(int,input().split())
s=input()
table=[]
for i in range(M):
    x,y=map(int,input().split())
    table.append((x-1,y-1))
edge=[[]for i in range(2*N)]
visit=[0]*(2*N)
for x,y in table:
    if x==y:
        edge[2*x].append(2*x+1)
        visit[2*x+1]+=1
        continue
    if s[x]==s[y]:
        edge[2*x].append(2*y+1)
        edge[2*y].append(2*x+1)
        visit[2*x+1]+=1
        visit[2*y+1]+=1
        continue
    edge[2*x+1].append(2*y)
    edge[2*y+1].append(2*x)
    visit[2*x]+=1
    visit[2*y]+=1
S=set()
L=deque()

for i in range(2*N):
    if visit[i]==0:
        L.append(i)

while L:
    x=L.pop()
    S.add(x)
    for y in edge[x]:
        visit[y]-=1
        if visit[y]==0:
            L.append(y)
if len(S)!=2*N:
    print('Yes')
else:
    print('No')

Solution (Python):
from collections import deque
N, M = map(int, input().split())
S = input()


connect_label = [[0, 0] for i in range(N)]


queue = deque()


deleted_set = set()


G = [[] for i in range(N)]


for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
    connect_label[a][1 - (S[b] == "A")] += 1
    connect_label[b][1 - (S[a] == "A")] += 1


for i in range(N):
    if 0 in connect_label[i]:
        queue.append(i)


while queue:
    n = queue.pop()

    
    if n in deleted_set:
        continue

    
    for v in G[n]:
        connect_label[v][1 - (S[n] == "A")] -= 1
        
        if (v not in deleted_set) and (0 in connect_label[v]):
            queue.appendleft(v)
        
    deleted_set.add(n)


print("Yes" if len(deleted_set) != N else "No")

Solution (Python):
import sys

n, m = map(int, input().split())
s = input()
to_a = [set() for _ in range(n)]
to_b = [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":
			to_a[a-1].add(b-1)
			to_a[b-1].add(a-1)
		else:
			to_b[a-1].add(b-1)
			to_a[b-1].add(a-1)
	if s[a-1] == "B":
		if s[b-1] == "B":
			to_b[a-1].add(b-1)
			to_b[b-1].add(a-1)
		else:
			to_a[a-1].add(b-1)
			to_b[b-1].add(a-1)

not_valid = set([i for i in range(n) if len(to_a[i]) * len(to_b[i]) == 0])
cnt = 0


while not_valid:
	node = not_valid.pop()
	
	cnt += 1

	for next_node in to_a[node]:
		if next_node == node:
			continue
		if s[node] == "A":
			to_a[next_node].remove(node)
		else:
			to_b[next_node].remove(node)

		if len(to_a[next_node]) * len(to_b[next_node]) == 0:
			not_valid.add(next_node)

	for next_node in to_b[node]:
		if next_node == node:
			continue
		if s[node] == "A":
			to_a[next_node].remove(node)
		else:
			to_b[next_node].remove(node)

		if len(to_a[next_node]) * len(to_b[next_node]) == 0:
			not_valid.add(next_node)

	

if cnt == n:
	print("No")
else:
	print("Yes")

Solution (Python):
import sys

n, m = map(int, input().split())
s = input()
to_a = [set() for _ in range(n)]
to_b = [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":
			to_a[a-1].add(b-1)
			to_a[b-1].add(a-1)
		else:
			to_b[a-1].add(b-1)
			to_a[b-1].add(a-1)
	if s[a-1] == "B":
		if s[b-1] == "B":
			to_b[a-1].add(b-1)
			to_b[b-1].add(a-1)
		else:
			to_a[a-1].add(b-1)
			to_b[b-1].add(a-1)

not_valid = set([i for i in range(n) if len(to_a[i]) * len(to_b[i]) == 0])
cnt = 0


while not_valid:
	node = not_valid.pop()
	
	cnt += 1

	for next_node in to_a[node]:
		if next_node == node:
			continue
		if s[node] == "A":
			to_a[next_node].remove(node)
		else:
			to_b[next_node].remove(node)

		if len(to_a[next_node]) * len(to_b[next_node]) == 0:
			not_valid.add(next_node)

	for next_node in to_b[node]:
		if next_node == node:
			continue
		if s[node] == "A":
			to_a[next_node].remove(node)
		else:
			to_b[next_node].remove(node)

		if len(to_a[next_node]) * len(to_b[next_node]) == 0:
			not_valid.add(next_node)

	

if cnt == n:
	print("No")
else:
	print("Yes")

Solution (Python):





"""
GC027 C
"""

n,m = map(int,input().split())
s = bytes(input(),'utf-8')
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]
import array as ar
remain = ar.array('b',[1 for i in range(n)])
from collections import defaultdict
graphAB = defaultdict(list)

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)



def incrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]+=1
    if s[adj-1] == 66:
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]-=1
    if s[adj-1] == 66:
        bli[node-1]-=1


def adjAB(node):
    if ali[node-1] and bli[node-1]:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        remain[i-1] = 0
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)
            remain[i-1] = 0


while bool(visitset):
    i = visitset.pop()
    for j in filter(lambda x:remain[x-1],graphAB[i]):
        
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
            remain[j-1] = 0

if set(remain)=={0}:
    print('No')
else:
    print('Yes')

Solution (Python):





"""
GC027 C
"""

n,m = map(int,input().split())
s = bytearray(input(),'utf-8')
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]
from collections import defaultdict
graphAB = defaultdict(list)

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)



def incrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]+=1
    if s[adj-1] == 66:
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]-=1
    if s[adj-1] == 66:
        bli[node-1]-=1


def adjAB(node):
    if ali[node-1] and bli[node-1]:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 67
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)

while bool(visitset):
    
    
    
    i = visitset.pop()
    for j in filter(lambda x: s[x-1]!=67,graphAB[i]):
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
    s[i-1] = 67




sset= set(s)
sset.add(67)
sset.remove(67)
if bool(sset):
    print('Yes')
else:
    print('No')

Solution (Python):





"""
GC027 C
"""

n,m = map(int,input().split())
s = bytearray(input(),'utf-8')
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]
from collections import defaultdict
graphAB = defaultdict(list)

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)



def incrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]+=1
    if s[adj-1] == 66:
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]-=1
    if s[adj-1] == 66:
        bli[node-1]-=1



graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 67
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not (ali[i-1] and bli[i-1]):
            visitset.add(i)

while bool(visitset):
    
    
    
    i = visitset.pop()
    for j in filter(lambda x: s[x-1]!=67,graphAB[i]):
        decrementAB(j,i)
        if not (ali[j-1] and bli[j-1]):
            visitset.add(j)
    s[i-1] = 67




sset= set(s)
sset.add(67)
sset.remove(67)
if bool(sset):
    print('Yes')
else:
    print('No')

Solution (Python):





"""
GC027 C
"""

n,m = map(int,input().split())
s = bytearray(input(),'utf-8')
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]
from collections import defaultdict
graphAB = defaultdict(list)

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)



def incrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]+=1
    if s[adj-1] == 66:
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]-=1
    if s[adj-1] == 66:
        bli[node-1]-=1


def adjAB(node):
    if ali[node-1] and bli[node-1]:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 67
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)

while bool(visitset):
    
    
    
    i = visitset.pop()
    for j in filter(lambda x: s[x-1]!=67,graphAB[i]):
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
    s[i-1] = 67




sset= set(s)
sset.add(67)
sset.remove(67)
if bool(sset):
    print('Yes')
else:
    print('No')

Solution (Python):





"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]
from collections import defaultdict
graphAB = defaultdict(list)

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)



def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1


def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)

while bool(visitset):
    
    
    
    i = visitset.pop()
    for j in filter(lambda x: s[x-1]!='C',graphAB[i]):
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
    s[i-1] = 'C'




sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')

Solution (Python):





"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]
from collections import defaultdict
graphAB = defaultdict(list)

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)



def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1


def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    
    
    
    i = visitset.pop()
    gen = (j for j in graphAB[i] if s[j-1]!='C')
    for j in gen:
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
    s[i-1] = 'C'




sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')

Solution (Python):





"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]


def addEdge(graph,u,v):
    graph[u].append(v)


from collections import defaultdict
graphAB = defaultdict(list)

def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1

for i,j in edges:
    addEdge(graphAB,i,j)
    addEdge(graphAB,j,i)

def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    
    
    
    i = visitset.pop()
    for j in graphAB[i]:
        if s[j-1] != 'C':
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
    s[i-1] = 'C'




sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')

Solution (Python):





"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]


def addEdge(graph,u,v):
    graph[u].add(v)


from collections import defaultdict
graphAB = defaultdict(set)

def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1

for i,j in edges:
    addEdge(graphAB,i,j)
    addEdge(graphAB,j,i)

def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    
    
    
    i = visitset.pop()
    for j in graphAB[i]:
        if s[j-1] != 'C':
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
    s[i-1] = 'C'




sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')

Solution (Python):
import collections

n,m = map(int,input().split())
s = list(str(input()))
key = collections.deque()
lis = [[] for i in range(n)]
li = [{"A":0,"B":0} for i in range(n)]

for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
  li[a-1][s[b-1]] += 1
  li[b-1][s[a-1]] += 1
  
ans = [0 for i in range(n)]

for i in range(n):
  if li[i]["A"] == 0 or li[i]["B"] == 0:
    key.append(i)
    ans[i] = 1
    
while len(key) > 0:
  num = key.popleft()
  for nu in lis[num]:
    li[nu][s[num]] -= 1
    if li[nu]["A"] == 0 or li[nu]["B"] == 0:
      if ans[nu] == 0:
        key.append(nu)
        ans[nu] = 1

if sum(ans) == n:print("No")
else:print("Yes")

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(10**8)

N,M = map(int, input().split())
s = list(input())

'''
A
1 ~ N -> mod0
N+1 ~ 2N -> mod1

B
1 ~ N -> mod2
N+1 ~ 2N -> mod3
'''

lines = [[] for i in range(2*N)]
for _ in range(M):
    a,b = map(int, input().split())
    a-=1
    b-=1
    sa, sb = s[a], s[b]
    if sa == sb:
        lines[a].append(b+N)
        lines[b].append(a+N)
    else:
        lines[a+N].append(b)
        lines[b+N].append(a)

ed = [0]*(2*N)

def dfs(s):
    global ed
    ed[s] = 1
    for t in lines[s]:
        if ed[t] == 1: 
            print('Yes')
            sys.exit()
        elif ed[t] == 0:
            dfs(t)
    ed[s] = 2

for s in range(N):
    if ed[s] == 0:
        dfs(s)

print('No')

Solution (Python):
import queue
import sys
input = sys.stdin.readline


def toab(s, ab, node):
    toa, tob = False, False
    for k in ab:
        if k not in node:
            continue
        if s[k - 1] == 'A':
            toa = True
            if tob:
                return True
        elif s[k - 1] == 'B':
            tob = True
            if toa:
                return True
    return False


ab = {}
node = {}
N, M = map(int, input().split())
s = input()
for i in range(M):
    a, b = map(int, input().split())
    if a not in ab:
        ab[a] = {}
    ab[a][b] = True
    if b not in ab:
        ab[b] = {}
    ab[b][a] = True
    node[a] = True
    node[b] = True

for i in range(N + 1):
    if i not in node:
        continue
    q = queue.Queue()
    q.put(i)
    while not q.empty():
        j = q.get()
        if j in node and not toab(s, ab[j], node):
            node.pop(j)
            for k in ab[j]:
                if k in node:
                    q.put(k)

if not node:
    print('No')
else:
    print('Yes')

Solution (Python):
import collections
n,m = map(int,input().split())
s = list(input())
g = [[] for i in range(0,n)]
ab = [{"A":0,"B":0}for _ in range(0,n)]
for i in range(0,m):
    A,B = map(int,input().split())
    g[A-1].append(B-1)
    g[B-1].append(A-1)
    ab[A-1][s[B-1]] += 1
    ab[B-1][s[A-1]] += 1

visit = [0 for i in range(0,n)]
que = collections.deque()
for i in range(0,n):
    if ab[i]["A"] == 0 or ab[i]["B"] == 0:
        que.append(i)
        visit[i] = 1

while len(que) > 0:
    q = que.popleft()
    for j in g[q]:
        ab[j][s[q]] -= 1
        if (ab[j]["A"] == 0 or ab[j]["B"] == 0)and visit[j] == 0:
            que.append(j)
            visit[j] = 1
if sum(visit) == n:
    print("No")
else:
    print("Yes")

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
s = input()
G = [[] for _ in range(2 * N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    if s[a] == s[b]:
        G[a].append(b + N)
        G[b].append(a + N)
    else:
        G[a + N].append(b)
        G[b + N].append(a)

status = [0] * (2 * N) 
def dfs(v):
    if status[v] == 1:
        print('Yes')
        exit()
    elif status[v] == 0:
        status[v] = 1
        for u in G[v]:
            dfs(u)
        status[v] = 2

for v in range(2 * N):
    dfs(v)
print('No')

Solution (Python):
from heapq  import heappush, heappop

N,M=map( int, raw_input().split() )
S="z"+raw_input()
num=[ [ 0 for i in range(2) ] for j in range(N+1) ] 

nl= [ [] for j in range(N+1) ] 

deleted=[ 0 for j in range(N+1) ] 

for i in range(M):
	a,b=map( int, raw_input().split() )
	if not b in nl[a]:
		nl[a].append(b)
		nl[b].append(a)
		if S[b]=="A":  num[a][0]+=1
		elif S[b]=="B":  num[a][1]+=1
		if S[a]=="A":  num[b][0]+=1
		elif S[a]=="B":  num[b][1]+=1

hq=[]

for i in range(1,N+1):
	if num[i][0]==0 or num[i][1]==0:
		heappush(hq,i)



while hq:
	x=heappop(hq)
	if deleted[x]==1: continue
	if num[x][0]==0 or num[x][1]==0:

		deleted[x]=1
		for u in nl[x]:
			if deleted[u]==0:
				if S[x]=="A": num[u][0]-=1						
				elif S[x]=="B": num[u][1]-=1
			
			if ( num[u][0]==0 or num[u][1]==0 ) and deleted[u]==0:
				heappush(hq,u)

				
if sum(deleted[1:])==N:
	print "No"
else:
	print "Yes"

Solution (Python):
from heapq  import heappush, heappop

N,M=map( int, raw_input().split() )
S="z"+raw_input()
num=[ [ 0 for i in range(2) ] for j in range(N+1) ] 

nl= [ [] for j in range(N+1) ] 

deleted=[ 0 for j in range(N+1) ] 

for i in range(M):
	a,b=map( int, raw_input().split() )
	if not b in nl[a]:
		nl[a].append(b)
		nl[b].append(a)
		if S[b]=="A":  num[a][0]+=1
		elif S[b]=="B":  num[a][1]+=1
		if S[a]=="A":  num[b][0]+=1
		elif S[a]=="B":  num[b][1]+=1

hq=[]

for i in range(1,N+1):
	if num[i][0]==0 or num[i][1]==0:
		heappush(hq,i)



while hq:
	x=heappop(hq)
	if deleted[x]==1: continue
	if num[x][0]==0 or num[x][1]==0:

		deleted[x]=1
		for u in nl[x]:
			if deleted[u]==0:
				if S[x]=="A": num[u][0]-=1						
				elif S[x]=="B": num[u][1]-=1
			
		
			if ( num[u][0]==0 or num[u][1]==0 ) and deleted[u]==0:
				heappush(hq,u)
			

				

	





if sum(deleted[1:])==N:
	print "No"
else:
	print "Yes"

Solution (Python):
'''
https://beta.atcoder.jp/contests/agc027/submissions/3201641
'''
n, m = map(int, input().split())
s = list(input())

deg = [{'A':0, 'B':0} for _ in range(n)]  
g = [list() for _ in range(n)]  

for i in range(m):  
    x, y = map(int, input().split())
    x, y = x - 1, y - 1  
    deg[x][s[y]] += 1  
    deg[y][s[x]] += 1  
    g[x].append(y)  
    g[y].append(x)  

was = [False for _ in range(n)]  
que = []  

for i in range(n):  
    if deg[i]['A'] == 0 or deg[i]['B'] == 0:  
        que.append(i)  
        was[i] = True  

for q in que:  
    for j in g[q]:  
        deg[j][s[q]] -= 1  
        if deg[j]['A'] == 0 or deg[j]['B'] == 0:  
            if not was[j]:  
                was[j] = True
                que.append(j)  



print('No' if len(que) == n else 'Yes')

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
s = input()
links = [[] for _ in range(2*n)]
visit = [0] * n *2
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if s[a] == s[b]:
      links[a].append(b+n)
      links[b].append(a+n)
    else:
      links[a+n].append(b)
      links[b+n].append(a)
def dfs(v):
  visit[v] = 1
  for i in links[v]:
    if visit[i] == 1:
      print("Yes")
      exit()
    elif visit[i] == 0:
      dfs(i)
  visit[v] = -1
  
for i in range(n):
  if visit[i] == 0:
    dfs(i)
print("No")

Solution (Python):
from collections import defaultdict
N, M = map( int, input().split())
S = list( input())
E = [ list( map( int, input().split())) for _ in range(M)]
V = [ 1 for _ in range(N)]
Edges = [set() for _ in range(N)]
A = [0]*N
B = [0]*N
d = defaultdict(int)
for i in range(M):
    a, b = E[i]
    a, b = a-1, b-1
    a, b = min(a,b), max(a,b)
    Edges[a].add(b)
    Edges[b].add(a)
    if d[(a,b)] == 1:
        continue
    else:
        d[(a,b)] += 1
    if a == b:
        if S[a] == 'A':
            A[a] += 1
        else:
            B[a] += 1
        continue
    if S[a] == 'A':
        A[b] += 1
    else:
        B[b] += 1
    if S[b] == 'B':
        B[a] += 1
    else:
        A[a] += 1
T = set()

for i in range(N):
    if A[i] == 0 or B[i] == 0:
        T.add(i)
while T:
    n = T.pop()
    V[n] = 0
    for m in Edges[n]:
        if V[m] == 1:
            if S[n] == 'A':
                A[m] -= 1
                if A[m] == 0:
                    T.add(m)
            else:
                B[m] -= 1
                if B[m] == 0:
                    T.add(m)
                
if sum(V) == 0:
    print('No')
else:
    print('Yes')

Solution (Python):
from collections import defaultdict
N, M = map( int, input().split())
S = list( input())
E = [ list( map( int, input().split())) for _ in range(M)]
V = [ 1 for _ in range(N)]
Edges = [[] for _ in range(N)]
A = [0]*N
B = [0]*N
d = defaultdict(int)
for i in range(M):
    a, b = E[i]
    a, b = a-1, b-1
    a, b = min(a,b), max(a,b)
    Edges[a].append(b)
    Edges[b].append(a)
    if d[(a,b)] == 1:
        continue
    else:
        d[(a,b)] += 1
    if a == b:
        if S[a] == 'A':
            A[a] += 1
        else:
            B[a] += 1
        continue
    if S[a] == 'A':
        A[b] += 1
    else:
        B[b] += 1
    if S[b] == 'B':
        B[a] += 1
    else:
        A[a] += 1
T = set([])

for i in range(N):
    if A[i] == 0 or B[i] == 0:
        T.add(i)
while T:
    n = T.pop()
    V[n] = 0
    for m in set(Edges[n]):
        if V[m] == 1:
            if S[n] == 'A':
                A[m] -= 1
                if A[m] == 0:
                    T.add(m)
            else:
                B[m] -= 1
                if B[m] == 0:
                    T.add(m)
                
if sum(V) == 0:
    print('No')
else:
    print('Yes')

Solution (Python):

from collections import deque

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


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
    

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")

Solution (Python):
import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        
        print('No')
        exit()
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')

Solution (Python):
import sys

sys.setrecursionlimit(200000)


def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)


def close(v, i):
    j = int(s[v] == 'B')
    for u in links[v][i].copy():
        if not able[u]:
            continue
        links[u][j].discard(v)
        if not links[u][j]:
            able[u] = False
            close(u, j ^ 1)


n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)

for v in range(n):
    if able[v]:
        continue
    close(v, bool(links[v][1]))

print('Yes' if any(able) else 'No')