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):
from collections import deque

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

S = []
for i in s: 
    if i == "A": S.append(0)
    else: S.append(1)


R = [list() for _ in range(N)]


C = [[0, 0] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    R[a-1].append(b-1)
    R[b-1].append(a-1)
    C[a-1][S[b-1]] += 1
    C[b-1][S[a-1]] += 1

O = [0] * N 
q = deque() 
for i in range(N):
    if C[i][0] * C[i][1] == 0: 
        q.append(i)
        O[i] = 1

while q:
    x = q.popleft()
    for v in R[x]:
        C[v][S[x]] -= 1
        if C[v][S[x]] == 0 and O[v] == 0:
            O[v] = 1
            q.append(v)

if sum(O) == N:
    answer = "No"
else:
    answer = "Yes"

print(answer)

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

sl = list(input())
abl = [list(map(int,input().split())) for _ in range(m)]


from collections import defaultdict
dic = defaultdict(list)

in_edge = [[0, 0] for i in range(n)]
for a, b in abl:
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)
    if sl[b-1] == "A":
        in_edge[a-1][0] += 1
    else:
        in_edge[a - 1][1] += 1
    if a != b:
        if sl[a-1] == "A":
            in_edge[b - 1][0] += 1
        else:
            in_edge[b - 1][1] += 1

used = [0 for i in range(n)]
removes = []
for idx, (a,b) in enumerate(in_edge):
    if a == 0 or b == 0:
        removes.append(idx)
        used[idx] = 1

ans = 0
while removes:
    ans += 1
    v = removes.pop()
    for w in dic[v]:
        if v != w:
            if sl[v] == "A":
                in_edge[w][0] -= 1
                if in_edge[w][0] == 0 and used[w] == 0:
                    removes.append(w)
                    used[w] = 1
            else:
                in_edge[w][1] -= 1
                if in_edge[w][1] == 0 and used[w] == 0:
                    removes.append(w)
                    used[w] = 1

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

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    s = input()
    way = [[] for _ in range(n)]
    nway = [[0,0] for i in range(n)]
    for _ in range(m):
        a,b = map(int,ipt().split())
        a -= 1
        b -= 1
        way[a].append(b)
        way[b].append(a)
        if s[a] == "A":
            nway[b][0] += 1
        else:
            nway[b][1] += 1
        if s[b] == "A":
            nway[a][0] += 1
        else:
            nway[a][1] += 1
    al = [0]*n

    q = deque()
    for i,wi in enumerate(nway):
        if wi[0] == 0 or wi[1] == 0:
            q.append(i)

    while q:
        qi = q.pop()
        al[qi] = -1
        if s[qi] == "A":
            x = 0
        else:
            x = 1
        for i in way[qi]:
            if al[i] == 0:
                if nway[i][x] == 1:
                    q.append(i)
                else:
                    nway[i][x] -= 1

    if 0 in al:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

n, m = nm()
s = list(map(lambda x: ord(x) - ord('A'), list(ns())))
G = [list() for _ in range(n)]
w = [[0, 0] for _ in range(n)]
for _ in range(m):
  u, v = nm()
  u -= 1; v -= 1
  G[u].append(v)
  G[v].append(u)
  w[u][s[v]] += 1
  w[v][s[u]] += 1

dele = [0]*n
q = deque()
for v in range(n):
  if not w[v][0] * w[v][1]:
    q.append(v)
    dele[v] = 1
while q:
  v = q.popleft()
  for x in G[v]:
    w[x][s[v]] -= 1
    if w[x][s[v]] == 0 and not dele[x]:
      dele[x] = 1
      q.append(x)
print('Yes' if sum(dele) < n else 'No')

Solution (Python):
import sys

input=sys.stdin.readline

def main():
    N,M=map(int,input().split())
    s=input()
    dic={"A":[0 for i in range(N)],"B":[0 for i in range(N)]}
    edge=[[] for i in range(N)]

    for i in range(M):
        a,b=map(int,input().split())
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)
        dic[s[a]][b]+=1
        dic[s[b]][a]+=1

    que=set([])
    check=0
    for i in range(N):
        if dic["A"][i]==0 or dic["B"][i]==0:
            que.add(i)
            dic["A"][i]=float("inf")
            dic["B"][i]=float("inf")

    while que:
        v=que.pop()
        check+=v+1
        for nv in edge[v]:
            dic[s[v]][nv]-=1
            if dic["A"][nv]==0 or dic["B"][nv]==0:
                dic["A"][nv]=float("inf")
                dic["B"][nv]=float("inf")
                que.add(nv)

    if check==N*(N+1)//2:
        print("No")
    else:
        print("Yes")

if __name__=="__main__":
    main()

Solution (Python):
import sys

input=sys.stdin.readline

def main():
    N,M=map(int,input().split())
    s=input()
    dic={"A":[0 for i in range(N)],"B":[0 for i in range(N)]}
    edge=[[] for i in range(N)]

    for i in range(M):
        a,b=map(int,input().split())
        a-=1;b-=1
        edge[a].append(b)
        edge[b].append(a)
        dic[s[a]][b]+=1
        dic[s[b]][a]+=1

    que=set([])
    check=0
    for i in range(N):
        if dic["A"][i]==0 or dic["B"][i]==0:
            que.add(i)


    while que:
        v=que.pop()
        check+=v+1
        dic["A"][v]=float("inf")
        dic["B"][v]=float("inf")
        for nv in edge[v]:
            dic[s[v]][nv]-=1
            if dic["A"][nv]==0 or dic["B"][nv]==0:
                que.add(nv)

    if check==N*(N+1)//2:
        print("No")
    else:
        print("Yes")

if __name__=="__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

N, M = map(int, input().split())
s = input()[:-1]
G = [[] for _ in range(N)]
A = [0]*N
B = [0]*N

for _ in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

q = deque([])
removed = [False]*N

for v in range(N):
    for nv in G[v]:
        if s[nv]=='A':
            A[v] += 1
        else:
            B[v] += 1
    
    if A[v]==0 or B[v]==0:
        q.append(v)
        removed[v] = True

while q:
    v = q.popleft()
    
    for nv in G[v]:
        if removed[nv]:
            continue
        
        if s[v]=='A':
            A[nv] -= 1
        else:
            B[nv] -= 1
        
        if A[nv]==0 or B[nv]==0:
            q.append(nv)
            removed[nv] = True

if False in removed:
    print('Yes')
else:
    print('No')

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())
s = input()

g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

count = [[0, 0] for _ in range(n)]
bad = []

for i in range(n):
    for v in g[i]:
        if s[v] == 'A':
            count[i][0] += 1
        else:
            count[i][1] += 1
    if count[i][0]*count[i][1] == 0:
        bad.append(i)


visited = [False]*n
while bad:
    v = bad.pop()
    if visited[v]:
        continue
    visited[v] = True
    for w in g[v]:
        if not visited[w]:
            if s[v] == 'A':
                count[w][0] -= 1
            else:
                count[w][1] -= 1
            if count[w][0]*count[w][1] == 0:
                bad.append(w)

for i in range(n):
    if count[i][0]*count[i][1] > 0:
        print('Yes')
        exit()

print('No')

Solution (Python):
n, m = map(int, input().split())
s = input()

g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

count = [[0, 0] for _ in range(n)]
bad = []

for i in range(n):
    for v in g[i]:
        if s[v] == 'A':
            count[i][0] += 1
        else:
            count[i][1] += 1
    if count[i][0]*count[i][1] == 0:
        bad.append(i)


visited = [False]*n
while bad:
    v = bad.pop()
    if visited[v]:
        continue
    visited[v] = True
    for w in g[v]:
        if not visited[w]:
            if s[v] == 'A':
                count[w][0] -= 1
            else:
                count[w][1] -= 1
            if count[w][0]*count[w][1] == 0:
                bad.append(w)

for i in range(n):
    if count[i][0]*count[i][1] > 0:
        print('Yes')
        exit()

print('No')

Solution (Python):
def main():
    N, M = map(int, input().split())
    S = [i == "B" for i in input()]
    ab = [list(map(int, input().split())) for _ in [0]*M]
    graph = [set() for _ in [0]*N]
    [graph[a-1].add(b-1) for a, b in ab]
    [graph[b-1].add(a-1) for a, b in ab]

    status = [[0, 0] for _ in [0]*N]

    for i in range(N):
        for j in graph[i]:
            status[i][S[j]] += 1

    que = []
    for i, (p, q) in enumerate(status):
        if (p == 0) ^ (q == 0):
            que.append(i)

    while que:
        i = que.pop()
        c = S[i]
        for j in graph[i]:
            if i != j:
                graph[j].remove(i)
            status[j][c] -= 1
            p, q = status[j]
            if (p == 0) ^ (q == 0):
                que.append(j)
        graph[i] = set()

    for i in graph:
        if i:
            print("Yes")
            return
    print("No")


main()

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline
    n, m = map(int, input().split())
    s = [i == "B" for i in input()]
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    g2 = [[0, 0] for _ in [0]*n]

    for i in range(n):
        for j in g[i]:
            g2[i][s[j]] += 1

    ss = []
    for i, (j, k) in enumerate(g2):
        if (j == 0 and k > 0) or (j > 0 and k == 0):
            ss.append(i)

    while ss:
        i = ss.pop()
        c = s[i]
        for j in g[i]:
            if i != j:
                g[j].remove(i)
            g2[j][c] -= 1
            p, q = g2[j]
            if (p == 0) ^ (q == 0):
                ss.append(j)
        g[i] = set()

    for i in g:
        if len(i) > 0:
            print("Yes")
            return
    print("No")


main()

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline
    n, m = map(int, input().split())
    s = [i == "B" for i in input()]
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    g2 = [[0, 0] for _ in [0]*n]

    for i in range(n):
        for j in g[i]:
            g2[i][s[j]] += 1

    ss = []
    for i, (j, k) in enumerate(g2):
        if (j == 0 and k > 0) or (j > 0 and k == 0):
            ss.append(i)

    while ss:
        i = ss.pop()
        c = s[i]
        for j in g[i]:
            if i != j:
                g[j].remove(i)
            g2[j][c] -= 1
            p, q = g2[j]
            if (p == 0 and q > 0) or (p > 0 and q == 0):
                ss.append(j)
        g[i] = set()

    for i in g:
        if len(i) > 0:
            print("Yes")
            return
    print("No")


main()

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
S = ["?"] + list(input())[: -1]
e = dd(set)
a = [0] * (N + 1)
b = [0] * (N + 1)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].add(v)
  e[v].add(u)

s = []
for x in range(1, N + 1):
  for y in e[x]:
    if S[y] == "A": a[x] += 1
    if S[y] == "B": b[x] += 1
  if a[x] == 0 or (b[x] == 0): s.append(x)

vis = [0] * (N + 1)
while len(s):
  x = s.pop()
  if vis[x]: continue
  vis[x] = 1
  for y in e[x]:
    if x == y: continue
    if S[x] == "A": a[y] -= 1
    if S[x] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): s.append(y)
 
if sum(vis) < N: print("Yes")
else: print("No")

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
def check(E):
    L = []
    n = len(E)
    done = [0] * n
    checking = [0] * n
    Q = []
    for i in range(n)[::-1]:
        Q.append(~i)
        Q.append(i)
    while Q:
        j = Q.pop()
        if j < 0:
            if done[~j]: continue
            done[~j] = 1
            L.append(~j)
            checking[~j] = 0
            continue
        if done[j]: continue
        checking[j] = 1
        for k in E[j]:
            if checking[k]:
                return 1
            Q.append(~k)
            Q.append(k)
    return 0

N, M = map(int, input().split())
S = [ord(a)-65 for a in input()]
X = [[] for _ in range(N*2)]

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if S[a] == S[b]:
        X[a].append(b+N)
        X[b].append(a+N)
    else:
        X[a+N].append(b)
        X[b+N].append(a)

print("Yes" if check(X) else "No")

Solution (Python):
n, m = map(int, input().split())
s = input()
G = [[] for _ in range(n)]
A = [0]*n
B = [0]*n
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if a==b:
    G[a].append(b)
    if s[b] == "A":
      A[a] += 1
    else:
      B[a] += 1
  else:
    G[a].append(b)
    G[b].append(a)
    if s[b] == "A":
      A[a] += 1
    else:
      B[a] += 1
    if s[a] == "A":
      A[b] += 1
    else:
      B[b] += 1
stack = []
cnt = 0
for i in range(n):
  if (not A[i]) or (not B[i]):
    stack.append(i)
while stack:
  v = stack.pop()
  cnt += 1
  if s[v] == "A":
    for nv in G[v]:
      A[nv] -= 1
      if B[nv] > 0 and A[nv] == 0:
        stack.append(nv)
  else:
    for nv in G[v]:
      B[nv] -= 1
      if A[nv] > 0 and B[nv] == 0:
        stack.append(nv)
if cnt == n:
  print("No")
else:
  print("Yes")

Solution (Python):
from collections import deque


n, m = map(int, input().split())
s = input()
info = [list(map(int, input().split())) for i in range(m)]

graph = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

v_num = [0] * n 
for i in range(n):
    if s[i] == "B":
        v_num[i] = 1

q = deque([])
used = [False] * n
v_cnt = [[0, 0] for i in range(n)]
for i in range(n):
    for j in graph[i]:
        v_cnt[j][v_num[i]] += 1
for i in range(n):
    if v_cnt[i][0] * v_cnt[i][1] == 0:
        q.append(i)
        used[i] = True

while q:
    pos = q.pop()
    for next_pos in graph[pos]:
        if used[next_pos]:
            continue
        v_cnt[next_pos][v_num[pos]] -= 1
        if v_cnt[next_pos][v_num[pos]] == 0:
            q.append(next_pos)
            used[next_pos] = True

for i in range(n):
    if not used[i]:
        print("Yes")
        exit()
print("No")

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

n,m = map(int,input().split())
s = input()
ab = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
ABs = [[0,0] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  if s[a-1] == "A":
    ABs[b][0] += 1
  else:
    ABs[b][1] += 1
  if s[b-1] == "A":
    ABs[a][0] += 1
  else:
    ABs[a][1] += 1
ablack = [-1 for i in range(n+1)]
ablack[0] = 0
stack = []
visited = [0 for i in range(n+1)]
for x in range(1,n+1):
  if ABs[x][0] == 0 or ABs[x][1] == 0:
    if s[x-1] == "A":
      ablack[x] = 0
    else:
      ablack[x] = 1
    stack.append(x)

while stack:
  x = stack.pop()
  if visited[x] == 1:
    continue
  visited[x] = 1
  for y in graph[x]:
    if visited[y] == 0:
      if ablack[x] == 0:
        ABs[y][0] -= 1
      else:
        ABs[y][1] -= 1
      if ABs[y][0] <= 0 or ABs[y][1] <= 0:
        if s[y-1] == "A":
          ablack[y] = 0
        else:
          ablack[y] = 1
        stack.append(y)
if ablack.count(-1) >= 1:
  print("Yes")
else:
  print("No")

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

N, M = map(int, input().split())
S = input().rstrip()
AB = []
AA = []
BB = []
for _ in range(M):
    a, b = map(int, input().split())
    if S[a-1] == "A" and S[b-1] == "B":
        AB.append((a-1, b-1))
    elif S[a-1] == "B" and S[b-1] == "A":
        AB.append((b-1, a-1))
    elif S[a-1] == "A":
        AA.append((a-1, b-1))
    else:
        BB.append((a-1, b-1))

graph = [set() for _ in range(2*N)]
to_A = [False]*N
to_B = [False]*N

for a, b in AB:
    graph[a].add(b)
    graph[b+N].add(a+N)
    to_B[a] = True
    to_A[b] = True

for a, b in AA:
    if to_B[a] or to_B[b]:
        graph[b+N].add(a)
        graph[a+N].add(b)

for a, b in BB:
    if to_A[a] or to_A[b]:
        graph[a].add(b+N)
        graph[b].add(a+N)


Color = [-1]*(2*N)
loop = False

for n in range(2*N):
    if Color[n] != -1:
        continue
    stack = [n]
    Color[n] = n
    while stack:
        p = stack[-1]
        update = False
        for np in graph[p]:
            if Color[np] == -1:
                update = True
                Color[np] = n
                stack.append(np)
                break
            elif len(stack) > 1:
                if np != stack[-2] and Color[np] == n:
                    loop = True
                    break
        if not update:
            stack.pop()
            Color[p] = 10**14
        if loop:
            break
    if loop:
        break

print("Yes" if loop else "No")

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.readline
N, M = map(int, readline().split())
Col = [1 if s == 'A' else 0 for s in readline().strip()]

Edge = [[] for _ in range(N)]
Dim = [[0, 0] for _ in range(N)]
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
    Dim[a][Col[b]] += 1
    Dim[b][Col[a]] += 1

Q = deque([i for i in range(N) if not min(Dim[i])])
used = set(Q)

while Q:
    vn = Q.pop()
    c = Col[vn]
    for vf in Edge[vn]:
        if vf in used:
            continue
        Dim[vf][c] -= 1
        if not Dim[vf][c]:
            used.add(vf)
            Q.appendleft(vf)

print('Yes' if len(used) < N else 'No')

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n, m = map(int, input().split())
    s = input().strip()
    ab = [tuple(map(int, input().split())) for _ in range(m)]
    edges = [[] for _ in range(n)]
    for a, b in ab:
        edges[a - 1].append(b - 1)
        edges[b - 1].append(a - 1)
    
    ab = [[0, 0] for i in range(n)]
    stack = []
    for i in range(n):
        for e in edges[i]:
            if s[e] == 'A':
                ab[i][0] += 1
            else:
                ab[i][1] += 1
        if ab[i][0] == 0 or ab[i][1] == 0:
            stack.append(i)
    
    deleted = [False for i in range(n)]
    while len(stack) > 0:
        q = stack.pop()
        if deleted[q]:
            continue
        deleted[q] = True
        for e in edges[q]:
            if not deleted[e]:
                if s[q] == 'A':
                    ab[e][0] -= 1
                    if ab[e][0] == 0:
                        stack.append(e)
                else:
                    ab[e][1] -= 1
                    if ab[e][1] == 0:
                        stack.append(e)
    
    for d in deleted:
        if not d:
            print("Yes")
            break
    else:
        print("No")


if __name__ == '__main__':
    main()

Solution (Python):
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

graph = [defaultdict(int) for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a][b] += 1
    if a != b:
        graph[b][a] += 1
























a_counts = [[0, v] for v in range(N)]
b_counts = [[0, v] for v in range(N)]
for v in range(N):
    for u, cnt in graph[v].items():
        if S[u] == 'A':
            a_counts[v][0] += cnt
        else:
            b_counts[v][0] += cnt
candidates = []
for c, v in a_counts + b_counts:
    if c == 0:
        candidates.append(v)

while candidates:
    v = candidates.pop()
    if not graph[v]:
        continue
    for u, cnt in list(graph[v].items()):
        if S[v] == 'A':
            a_counts[u][0] -= cnt
            if a_counts[u][0] == 0:
                candidates.append(u)
        else:
            b_counts[u][0] -= cnt
            if b_counts[u][0] == 0:
                candidates.append(u)
        del graph[u][v]
    graph[v] = {}



ok = any(graph)
if ok:
    print('Yes')
else:
    print('No')

Solution (Python):
def examC():
    N,M = LI()
    S = SI()
    V = [[] for _ in range(N)]
    ok = [1]*N
    acnt = [0]*N; bcnt = [0]*N
    for _ in range(M):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
        if S[a-1]=="A":
            acnt[b-1] +=1
        else:
            bcnt[b-1] +=1
        if S[b-1]=="A":
            acnt[a-1] +=1
        else:
            bcnt[a-1] +=1
    NGque = deque()
    for i in range(N):
        if acnt[i]==0 or bcnt[i]==0:
            ok[i]=0
            NGque.append(i)


    while(NGque):
        cur = NGque.pop()
        for i in V[cur]:
            if ok[i]==1:
                if S[cur] == "A":
                    acnt[i] -= 1
                else:
                    bcnt[i] -= 1
                if acnt[i] == 0 or bcnt[i] == 0:
                    ok[i] = 0
                    NGque.append(i)
    if max(ok)==1:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)

import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Solution (Python):

from collections import defaultdict, deque


def getlist():
	return list(map(int, input().split()))


def main():
	
	N, M = getlist()
	s = list(input())
	outE = defaultdict(list)
	inEA = defaultdict(int)
	inEB = defaultdict(int)
	E = set()
	for i in range(M):
		a, b = sorted(getlist())
		a = a - 1
		b = b - 1
		E.add((a, b))
	E = list(E)
	
	m = len(E)
	for i in range(m):
		a = E[i][0]
		b = E[i][1]
		outE[a].append(b)
		outE[b].append(a)
		if s[a] == "A":
			inEA[b] += 1
		else:
			inEB[b] += 1

		if s[b] == "A":
			inEA[a] += 1
		else:
			inEB[a] += 1
	
	Q = deque()
	for i in range(N):
		if inEA[i] == 0 or inEB[i] == 0:
			Q.append(i)

	visit = ["No"] * N
	check = ["Yes"] * N
	while Q:
		u = Q.popleft()
		if visit[u] == "Yes":
			continue
		visit[u] = "Yes"
		check[u] = "No"
		for v in outE[u]:
			if s[u] == "A":
				inEA[v] -= 1
				if inEA[v] == 0:
					check[v] = "No"
					Q.append(v)
			else:
				inEB[v] -= 1
				if inEB[v] == 0:
					check[v] = "No"
					Q.append(v)

	judge = "No"
	
	for i in range(N):
		if check[i] == "Yes":
			judge = "Yes"
	print(judge)

if __name__ == '__main__':
	main()

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

N, M = map(int, input().split())
s = input()
label = [0] * (N+1)
for i in range(N):
    if s[i] == 'B':
        label[i+1] = 1
adj = [[] for _ in range(N+1)]
ab_num = [[0, 0] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
    ab_num[a][label[b]] += 1
    ab_num[b][label[a]] += 1

stack = []
remain = [1] * (N+1)
for i in range(1, N+1):
    if ab_num[i][0] == 0 or ab_num[i][1] == 0:
        stack.append(i)
        remain[i] = 0

cnt = N - len(stack)
while stack:
    if cnt == 0:
        print('No')
        exit()
    v = stack.pop()
    for u in adj[v]:
        if remain[u]:
            if ab_num[u][label[v]] == 1:
                remain[u] = 0
                stack.append(u)
                cnt -= 1
            else:
                ab_num[u][label[v]] -= 1

print('Yes')

Solution (Python):
from collections import deque
import sys

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

s = input()

dic = {}
linkA = [0] * N
linkB = [0] * N
able = [True] * N

for i in range(M):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

    if s[a] == "A":
        linkA[b] += 1
    else:
        linkB[b] += 1

    if s[b] == "A":
        linkA[a] += 1
    else:
        linkB[a] += 1


q = deque([])

for i in range(N):

    if linkA[i] == 0 or linkB[i] == 0:
        able[i] = False
        q.append(i)

while len(q) > 0:

    now = q.popleft()
    

    if now in dic:
        for i in dic[now]:

            if s[now] == "A":
                linkA[i] -= 1
            else:
                linkB[i] -= 1


            if (linkA[i] <= 0 or linkB[i] <= 0) and able[i]:
                able[i] = False
                q.append(i)

for i in able:
    if i:
        print ("Yes")
        sys.exit()

print ("No")

Solution (Python):
def scc(E, n_vertex):
    
    
    
    import numpy as np
    from scipy.sparse import csr_matrix, csgraph
    A, B = np.array(E).T
    graph = csr_matrix((np.ones(len(E)), (A, B)), (n_vertex, n_vertex))
    n_components, labels = csgraph.connected_components(graph, connection='strong')
    return n_components, labels

N, M = map(int, input().split())
S = "_" + input()
E = []
for _ in range(M):
    a, b = map(int, input().split())
    if S[a]==S[b]:
        E.append([a, N+b])
        E.append([b, N+a])
    else:
        E.append([N+a, b])
        E.append([N+b, a])

n_components, _ = scc(E, 2*N+1)
if n_components == 2*N+1:
    print("No")
else:
    print("Yes")

Solution (Python):
N, M = map(int, input().split())
s = input()
C = [[0, 0] for _ in range(N)]
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    if s[b-1] == 'A':
        C[a-1][0]+=1
    else:
        C[a-1][1]+=1
    if s[a-1] == 'A':
        C[b-1][0]+=1
    else:
        C[b-1][1]+=1
    G[a-1].append(b-1)
    G[b-1].append(a-1)
que = []
deleted = [False]*N
for i in range(N):
    if C[i][0] == 0 or C[i][1] == 0:
        que.append(i)
        deleted[i] = True
while que:
    v = que.pop()
    if s[v] == 'A':
        i = 0
    else:
        i = 1
    for nv in G[v]:
        if deleted[nv]:
            continue
        C[nv][i]-=1
        if C[nv][i]==0:
            que.append(nv)
            deleted[nv] = True
if all(f for f in deleted):
    print('No')
else:
    print('Yes')

Solution (Python):
N,M=map(int,input().split())
S="0"+input()
E=[[] for i in range(N+1)]
AOUT=[0]*(N+1)
BOUT=[0]*(N+1)

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

    if S[x]=="A":
        AOUT[y]+=1
    else:
        BOUT[y]+=1

    if S[y]=="A":
        AOUT[x]+=1
    else:
        BOUT[x]+=1

from collections import deque
Q=deque()

USE=[0]*(N+1)

for i in range(N+1):
    if AOUT[i]==0 or BOUT[i]==0:
        Q.append(i)
        USE[i]=1

while Q:
    x=Q.pop()

    for to in E[x]:
        if USE[to]==0:
            if S[x]=="A":
                AOUT[to]-=1
            else:
                BOUT[to]-=1

            if AOUT[to]==0 or BOUT[to]==0:
                Q.append(to)
                USE[to]=1

if 0 in USE:
    print("Yes")
else:
    print("No")

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

"""
AABBAABBAABB..が作れることと同値
"""

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

N,M = map(int,input().split())
S = input().rstrip()

AB = [[int(x)-1 for x in row.split()] for row in sys.stdin.readlines()]


edge = []
for a,b in AB:
    s = S[a]; t = S[b]
    if s == t:
        edge.append((a+N,b))
        if a != b:
            edge.append((b+N,a))
    else:
        edge.append((a,b+N))
        edge.append((b,a+N))

row,col = zip(*edge)

graph = csr_matrix(([1]*len(row),(row,col)),(2*N,2*N))

n_component,_ = connected_components(graph,connection='strong')

answer = 'Yes' if n_component < 2*N else 'No'
print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(200000)
n, m = map(int, input().split())
s = input()
out = [set() for _ in range(n)]
count = [[0, 0] for _ in range(n)]
def f(c):
    if c == 'A': return 0
    else: return 1
for _ in range(m):
    a, b = map(int, input().split())
    if a == b:
        count[a-1][f(s[a-1])] += 1
    elif b-1 not in out[a-1]:
        count[a-1][f(s[b-1])] += 1
        count[b-1][f(s[a-1])] += 1
    out[a-1].add(b-1)
    out[b-1].add(a-1)
elim = set()
def eliminate(x):
    elim.add(x)
    c = f(s[x])
    for node in out[x]:
        if node not in elim:
            count[node][c] -= 1
            if count[node][0] * count[node][1] == 0:
                eliminate(node)
for i in range(n):
    if i not in elim and count[i][0] * count[i][1] == 0:
        eliminate(i)
if len(elim) < n: print('Yes')
else: print('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')