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: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
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):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    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

#print(graphAB)
#print(graphABopp)

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

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
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):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    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'

#print(graphAB)
#print(graphABopp)

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

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
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):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    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'

#print(graphAB)
#print(graphABopp)

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

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
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):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    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'

#print(graphAB)
#print(graphABopp)

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

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
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):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    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'

#print(graphAB)
#print(graphABopp)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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) #0 = 未訪問　1 = 訪問中 2 = 訪問済
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')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
			
		#	print "x,u,num:::",x,u,num
			if ( num[u][0]==0 or num[u][1]==0 ) and deleted[u]==0:
				heappush(hq,u)
			#	print "x,u,hq:::",x,u,hq

				

	

#print "num:::",num
#print "deleted:::",deleted
#print "nl:::",nl

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

Submission status: Accepted

Solution code:
'''
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)]  # deg[0 - (n - 1)][0 - 1] = 0
g = [list() for _ in range(n)]  # g[0 - (n - 1)] = []

for i in range(m):  # クエリを配列に代入
    x, y = map(int, input().split())
    x, y = x - 1, y - 1  # 1-indexed -> 0-indexed
    deg[x][s[y]] += 1  # 頂点 x に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    deg[y][s[x]] += 1  # 頂点 y に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    g[x].append(y)  # 頂点 x に隣接する頂点のリストに y を追加
    g[y].append(x)  # 頂点 y に隣接する頂点のリストに x を追加

was = [False for _ in range(n)]  # was[j] = True なら 頂点 j は que に追加済み
que = []  # A か B が隣接しないため, 連結リストから除外する頂点

for i in range(n):  # 全頂点をループ
    if deg[i]['A'] == 0 or deg[i]['B'] == 0:  # A か B が隣接しないなら
        que.append(i)  # 除外頂点リスト que に追加
        was[i] = True  #  was[j] = True は, 除外頂点リスト que に追加済を意味する

for q in que:  # A か B が隣接していない, 除外頂点リストの各頂点をループ（ que はループ中に追加されうる）
    for j in g[q]:  # 除外頂点に隣接する頂点をループ
        deg[j][s[q]] -= 1  # "除外頂点に隣接する頂点" に隣接する頂点の個数を管理 : 除外頂点の文字のカウントを減らす
        if deg[j]['A'] == 0 or deg[j]['B'] == 0:  # "除外頂点に隣接する頂点" に A か B が隣接しないなら
            if not was[j]:  # 頂点 j が que に追加済みの頂点でないなら, que に追加する / 追加済みなら, 隣接する頂点の個数管理は, 終了済み
                was[j] = True
                que.append(j)  # 除外頂点リスト que に追加, ループ回数増える

# 除外頂点を取り除いた後に, 頂点が残っていれば, AABB... を作成できる
# 頂点が残っていなければ, つまり, que に全ての頂点が入っていれば, AABB...を作成できない
print('No' if len(que) == n else 'Yes')

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C
from collections import deque

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
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]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        # gori~~~
        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')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main():
    n, m = map(int, stdin.readline().split())
    s = raw_input().strip()
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    e = [[set(), set()] for i in xrange(n)]
    for i in xrange(2 * m):
        dat[i] -= 1
    for i in xrange(m):
        x, y = dat[i*2], dat[i*2+1]
        e[x][s[y]=='B'].add(i)
        e[y][s[x]=='B'].add(i)
    st = []
    pu = st.append
    po = st.pop
    d = [0] * n
    for i in xrange(n):
        if not e[i][0] or not e[i][1]:
            pu(i)
            d[i] = 1
    while st:
        z = po()
        for j in xrange(2):
            for i in e[z][j]:
                x, y = dat[i*2], dat[i*2+1]
                if x == y:
                    continue
                if x == z:
                    x, y = y, x
                e[x][s[y]=='B'].discard(i)
                if not e[x][s[y]=='B'] and not d[x]:
                    d[x] = 1
                    pu(x)
            e[z][j].clear()
    for i in xrange(n):
        if e[i][0] and e[i][1]:
            print 'Yes'
            return
    print 'No'
main()

Submission status: Runtime Error

Solution code:
from collections import deque

N, M = map(int, input().split())
s = [list(input()) for i in range(N)]

S = []
for i in s: #S[i]=0なら頂点iのラベルは"A"、S[i]=1なら頂点iのラベルは"B"
    if i == "A": S.append(0)
    else: S.append(1)

#R[i]には頂点iと辺でつながっている頂点を入れる
R = [list() for _ in range(N)]
#C[i][0]には頂点iと辺でつながっているラベル"A"の数
#C[i][1]には頂点iと辺でつながっているラベル"B"の数
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 #ダメな頂点には1を入れる
q = deque() #調べる頂点の候補リスト
for i in range(N):
    if C[i][0] * C[i][1] == 0: #もし少なくとも"A","B"どちらかに行けないなら
        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)

Submission status: Runtime Error

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"][v]=float("inf")
            dic["B"][v]=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: Runtime Error

Solution code:
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 g[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)
        g[i] = set()

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


main()

Submission status: Runtime Error

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: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define FORW(a, b, c) for(int a = b; a >= c; --a)
#define fi first
#define se second
#define pb push_back
#define int long long

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 2e5 + 100;
const int oo = 1e18;
const int mod   = 1e9 + 7;

int n, m;
int name[N], cnt[N][2];
bool visit[N];
vector<int> vi[N];

void solve()    {
    queue<int> pq;

    int ans = n;
    FOR(i, 1, n) if(!(cnt[i][0] * cnt[i][1]))
        ans --, pq.push(i), visit[i] = true;
    while(!pq.empty())  {
        int u = pq.front(); pq.pop();
        for(auto v: vi[u]) if(!visit[v]){
            cnt[v][name[u]] --;
            if(!cnt[v][name[u]]) {
                visit[v] = 1;
                pq.push(v);
                ans --;
            }
        }
    }
    if(!ans) cout << "No";
    else cout << "Yes";
}

signed main()  {
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    ios_base::sync_with_stdio(false); cout.tie(0);
    cin >> n >> m;
    FOR(i, 1, n) {
        char c; cin >> c;
        name[i] = c - 'A';
    }
    FOR(i, 1, m)    {
        int u, v; cin >> u >> v;
        vi[u].pb(v); vi[v].pb(u);
        cnt[u][ name[v] ] ++;
        cnt[v][ name[u] ] ++;
    }
    return solve(), 0;
}

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)
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')

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
s = list(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')

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
s = list(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())
    out[a-1].add(b-1)
    out[b-1].add(a-1)
    count[a-1][f(s[b-1])] += 1
    count[b-1][f(s[a-1])] += 1
elim = set()
def eliminate(x, c):
    count[x][c] -= 1
    if count[x][0] & count[x][1] == 0:
        elim.add(x)
        for node in out[x]:
            if node not in elim:
                eliminate(node, f(s[x]))
for i in range(n):
    if count[i][0] & count[i][1] == 0:
        elim.add(i)
        for node in out[i]:
            if node not in elim:
                eliminate(node, f(s[i]))
if len(elim) < n: print('Yes')
else: print('No')