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:
n,m = map(int,input().split())
s = input()
aa = 0
ab = 0
bb = 0
for i in range(m):
  a,b = map(int,input().split())
  if s[a-1] + s[b-1] == "AA":
    aa += 1
  elif s[a-1]+s[b-1] == "BB":
    bb += 1
  else:
    ab += 1
if aa > 0 and bb > 0 and ab > 0:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
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"][v]=float("inf")
                dic["B"][v]=float("inf")
                que.add(nv)

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

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
#####segfunc#####
def segfunc(x, y):
    if x[0]>y[0]:
        return y
    elif x[0]<y[0]:
        return x
    elif x[1]>y[1]:
        return y
    else:
        return x
#################

#####ide_ele#####
ide_ele = [float("inf"),-1]
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k][0] += x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

import sys

input=sys.stdin.readline

def main():
    N,M=map(int,input().split())
    s=input()
    dic={"A":[[0,i] for i in range(N)],"B":[[0,i] 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][0]+=1
        dic[s[b]][a][0]+=1

    dic={moji:SegTree(dic[moji],segfunc,ide_ele) for moji in dic}

    while True:
        a,index=dic["A"].query(0,N)
        b,index2=dic["B"].query(0,N)
        if a==0:
            dic["A"].update(index,float("inf"))
            dic["B"].update(index,float("inf"))
            for v in edge[index]:
                dic[s[index]].update(v,-1)

        elif b==0:
            dic["A"].update(index2,float("inf"))
            dic["B"].update(index2,float("inf"))
            for v in edge[index2]:
                dic[s[index2]].update(v,-1)
        else:
            break

    check1=dic["A"].query(0,N)
    check2=dic["B"].query(0,N)
    if check1==check2==float("inf"):
        print("No")
    else:
        print("Yes")

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
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([])

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 = [False]*N

while q:
    v = q.popleft()
    removed[v] = True
    
    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)

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

Submission status: Wrong Answer

Solution code:
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)

visited = [False]*n

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


def dfs(x):
    stack = [x]
    while stack:
        v = stack.pop()
        if visited[v]:
            break
        visited[v] = True
        for w in g[v]:
            if not visited[w]:
                stack.append(w)
            if s[w] == 'A':
                count[v][0] += 1
            else:
                count[v][1] += 1


bad = []

for i in range(n):
    dfs(i)
    if count[i][0]*count[i][1] == 0:
        bad.append(i)

visited = [False]*n
while bad:
    v = bad.pop()
    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')

Submission status: Wrong Answer

Solution code:
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()
  vis[x] = 1
  for y in e[x]:
    if x == y: continue
    if vis[y]: continue
    vis[y] = 1
    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")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
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)

Q = dq([])
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): Q.append(x)

res = N
while len(Q):
  x = Q.popleft()
  res -= 1
  for y in e[x]:
    if x == y: continue
    e[y].discard(x)
    if S[x] == "A": a[y] -= 1
    if S[x] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): Q.append(y)

if res: print("Yes")
else: print("No")

Submission status: Wrong Answer

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

Q = dq([])
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): Q.append(x)

vis = [0] * (N + 1)
while len(Q):
  x = Q.popleft()
  vis[x] = 1
  for y in e[x]:
    if x == y: continue
    if vis[y]: continue
    vis[y] = 1
    if S[x] == "A": a[y] -= 1
    if S[x] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): Q.append(y)

if sum(vis) < N: print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
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)

Q = dq([])
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): Q.append(x)

vis = [0] * (N + 1)
while len(Q):
  x = Q.popleft()
  vis[x] = 1
  for y in e[x]:
    if x == y: continue
    e[y].discard(x)
    if S[x] == "A": a[y] -= 1
    if S[x] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): Q.append(y)

if sum(vis) < N: print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
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)

Q = dq([])
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): Q.append(x)

vis = [0] * (N + 1)
while len(Q):
  x = Q.popleft()
  vis[x] = 1
  for y in e[x]:
    if x == y: continue
    e[y].discard(x)
    if S[x] == "A": a[y] -= 1
    if S[y] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): Q.append(y)

if sum(vis) < N: print("Yes")
else: print("No")

Submission status: Wrong Answer

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

Q = dq([])
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): Q.append(x)

vis = [0] * (N + 1)
while len(Q):
  x = Q.popleft()
  vis[x] = 1
  for y in e[x]:
    if x == y: continue
    if vis[y]: continue
    vis[y] = 1
    if S[x] == "A": a[y] -= 1
    if S[y] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): Q.append(y)

if sum(vis) < N: print("Yes")
else: print("No")

Submission status: Wrong Answer

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

Q = dq([])
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): Q.append(x)

vis = [0] * (N + 1)
while len(Q):
  x = Q.popleft()
  vis[x] = 1
  for y in e[x]:
    if vis[y]: continue
    vis[y] = 1
    if S[x] == "A": a[y] -= 1
    if S[y] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): Q.append(y)

if sum(vis) < N: print("Yes")
else: print("No")

Submission status: Wrong Answer

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

Q = dq([])
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): Q.append(x)

vis = [0] * (N + 1)
while len(Q):
  x = Q.popleft()
  vis[x] = 1
  for y in e[x]:
    if vis[y]: continue
    if S[x] == "A": a[y] -= 1
    if S[y] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): Q.append(y)

if sum(vis) < N: print("Yes")
else: print("No")

Submission status: Wrong Answer

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

Q = dq([])
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): Q.append(x)

vis = [0] * (N + 1)
while len(Q):
  x = Q.popleft()
  vis[x] = 1
  for y in e[x]:
    if S[x] == "A": a[y] -= 1
    if S[y] == "B": b[y] -= 1
    if a[y] == 0 or (b[y] == 0): Q.append(y)

if sum(vis) < N: print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
S = list(input())[: -1]
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
for x in range(1, N + 1): e[0].append(x)

s = [~0, 0]
table = [-1] * (N + 1)
while len(s):
  x = s.pop()
  a = 0
  b = 0
  if x >= 0:
    if table[x] >= 0: continue
    for y in e[x]:
      if S[y - 1] == "A": a = 1
      if S[y - 1] == "B": b = 1
    if a and b: table[x] = 1
    else:
      table[x] = 0
      continue
    for y in e[x]:
      if x == y: continue
      if table[y] >= 0: continue
      s.append(~y)
      s.append(y)
  else:
    for y in e[~x]:
      if S[y - 1] == "A" and (table[y] == 1): a = 1
      if S[y - 1] == "B" and (table[y] == 1): b = 1
    table[~x] = a & b
  #print(table)
if a & b: print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
S = list(input())[: -1]
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
for x in range(1, N + 1): e[0].append(x)

s = [~0, 0]
table = [-1] * (N + 1)
while len(s):
  x = s.pop()
  a = 0
  b = 0
  if x >= 0:
    if table[x] >= 0: continue
    for y in e[x]:
      if S[y - 1] == "A": a = 1
      if S[y - 1] == "B": b = 1
    if a and b: table[x] = 1
    else:
      table[x] = 0
      continue
    for y in e[x]:
      if x == y: continue
      if table[y] == 1: continue
      s.append(~y)
      s.append(y)
  else:
    for y in e[~x]:
      if S[y - 1] == "A" and (table[y] == 1): a = 1
      if S[y - 1] == "B" and (table[y] == 1): b = 1
    table[~x] = a & b
  #print(table)
if a & b: print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
S = list(input())[: -1]
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
for x in range(1, N + 1): e[0].append(x)

s = [~0, 0]
table = [-1] * (N + 1)
while len(s):
  x = s.pop()
  a = 0
  b = 0
  if x >= 0:
    if table[x] >= 0: continue
    for y in e[x]:
      if S[y - 1] == "A": a = 1
      if S[y - 1] == "B": b = 1
    if a and b: table[x] = 1
    else:
      table[x] = 0
      continue
    for y in e[x]:
      if x == y: continue
      s.append(~y)
      s.append(y)
  else:
    for y in e[~x]:
      if S[y - 1] == "A" and (table[y] == 1): a = 1
      if S[y - 1] == "B" and (table[y] == 1): b = 1
    table[~x] = a & b

if a & b: print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
S = list(input())[: -1]
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
for x in range(1, N + 1): e[0].append(x)

s = [0]
table = [-1] * (N + 1)
while len(s):
  x = s.pop()
  a = 0
  b = 0
  if x >= 0:
    if table[x] >= 0: continue
    for y in e[x]:
      if S[y - 1] == "A": a = 1
      if S[y - 1] == "B": b = 1
    if a and b: table[x] = 1
    else:
      table[x] = 0
      continue
    for y in e[x]:
      if x == y: continue
      s.append(~y)
      s.append(y)
  else:
    for y in e[~x]:
      if S[y - 1] == "A" and (table[y] == 1): a = 1
      if S[y - 1] == "B" and (table[y] == 1): b = 1
    table[~x] = a & b
a = 0
b = 0
for y in e[0]:
  if S[y - 1] == "A" and (table[y] == 1): a = 1
  if S[y - 1] == "B" and (table[y] == 1): b = 1
if a & b: print("Yes")
else: print("No")

Submission status: Wrong Answer

Solution code:
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 if len(L) == n else 1

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] == 0:
        X[a].append(b+N)
    else:
        X[a+N].append(b)
        X[b+N].append(a)

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

Submission status: Wrong Answer

Solution code:
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] == 0:
        X[a].append(b+N)
    else:
        X[a+N].append(b)
        X[b+N].append(a)

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

Submission status: Wrong Answer

Solution code:
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()
  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")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
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
    elif s[a-1] == "B":
        ABs[b][1] += 1
    if s[b-1] == "A":
        ABs[a][0] += 1
    elif s[b-1] =="B":
        ABs[a][1] += 1
ablack = [-1 for i in range(n+1)]
ablack[0] = 0
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
        elif s[x-1] == "B":
            ablack[x] = 1
que = deque([])
visited = [0 for i in range(n+1)]
for i in range(1,n+1):
    if ablack[i] >= 0:
        que.append(i)
while que:
    x = que.pop()
    visited[x] = 1
    for y in graph[x]:
        if visited[y] == 0:
            if ablack[x] == 0:
                ABs[y][0] -= 1
            elif ablack[x] == 1:
                ABs[y][1] -= 1
            if ABs[y][0] == 0 or ABs[y][1] == 0:
                if s[y-1] == "A":
                    ablack[y] = 0
                elif s[y-1] == "B":
                    ablack[y] = 1
                que.append(y)
if ablack.count(-1) >= 1:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
print("No")

Submission status: Wrong Answer

Solution code:
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
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 = []
visited = [0 for i in range(n+1)]
for i in range(1,n+1):
    if ablack[i] >= 0:
        stack.append(i)
while stack:
    x = stack.pop()
    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) >= 2:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
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
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 = []
visited = [0 for i in range(n+1)]
for i in range(1,n+1):
    if ablack[i] >= 0:
        stack.append(i)
while stack:
    x = stack.pop()
    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")

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
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
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
que = deque([])
visited = [0 for i in range(n+1)]
for i in range(1,n+1):
    if ablack[i] >= 0:
        que.append(i)
while que:
    x = que.pop()
    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
                que.append(y)
if ablack.count(-1) >= 1:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
S = input().rstrip()
AB = []
AA = []
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))
    else:
        AA.append((a-1, b-1))

graph = [[] for _ in range(2*N)]

for a, b in AB:
    graph[a].append(b)
    graph[b+N].append(a+N)

for a, b in AA:
    if a == b:
        graph[a].append(a+N)
        graph[a+N].append(a)
    else:
        graph[a].append(b+N)
        graph[b+N].append(a)
        graph[b].append(a+N)
        graph[a+N].append(b)


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
S = input().rstrip()
AB = []
AA = []
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))
    else:
        AA.append((a-1, b-1))

graph = [[] for _ in range(2*N)]

for a, b in AB:
    graph[a].append(b)
    graph[b+N].append(a+N)

for a, b in AA:
    if a == b:
        graph[a].append(a+N)
        graph[a+N].append(a)
    else:
        graph[a].append(b+N)
        graph[b+N].append(a)
        graph[b].append(a+N)
        graph[a+N].append(b)


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

for n in range(2*N):
    if Color[n] != -3:
        continue
    stack = [n]
    Color[n] = n
    while stack:
        p = stack[-1]
        update = False
        for np in graph[p]:
            if Color[np] == -3:
                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] = n-1
        if loop:
            break
    if loop:
        break

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

Submission status: Wrong Answer

Solution code:
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()