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

Solution code:

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

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


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


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

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)


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

Submission status: Runtime Error

Solution code:


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


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


def deleteNode(graph,node):
    graph.pop(node,None)

from collections import defaultdict
graphAB = defaultdict(set)
graphABopp = defaultdict(set)

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

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

edgeset = set()
for i,j in edges:
    ii = min(i,j)
    jj = max(i,j)
    edgeset.add((ii,jj))

for i,j in edgeset:
    addEdge(graphAB,i,j)
    addEdge(graphABopp,j,i)
    incrementAB(i,j)
    if j!=i:
        incrementAB(j,i)


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


#def adjAB(node):
#    Aflag = 'A' in map(lambda x:s[x-1],graphAB[node])
#    Aflag = Aflag or 'A' in map(lambda x:s[x-1],graphABopp[node])
#    Bflag = 'B' in map(lambda x:s[x-1],graphAB[node])
#    Bflag = Bflag or 'B' in map(lambda x:s[x-1],graphABopp[node])
#    if Aflag and Bflag:
#        return(True)
#    else:
#        return(False)



visitset = set([i for i in set(graphAB.keys())|set(graphABopp.keys()) if not adjAB(i)])
#print(visitset)

while bool(visitset):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    i = visitset.pop()
    for j in graphAB[i]:
        if not adjAB(j):
            graphABopp[j].remove(i)
            decrementAB(j,i)
        else:
            graphABopp[j].remove(i)
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
            #print(visitset,'add')
    for j in graphABopp[i]:
        if not adjAB(j):
            graphABopp[j].remove(i)
            decrementAB(j,i)
        else:
            graphABopp[j].remove(i)
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
            #print(visitset,'add')
    graphAB.pop(i,None)
    graphABopp.pop(i,None)

#print(graphAB)
#print(graphABopp)


if graphAB == {} and graphABopp == {}:
    print('No')
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
s = input()
edge, connect = [[] for _ in range(N)], [{"A":0, "B":0} for _ in range(N)]
L, Q = [int(i) for i in range(1, N+1)], []

for _ in range(M):
    a, b = map(int, input().split())
    edge[a-1].append(b)
    connect[a-1][s[b-1]] += 1
    if a != b:
        edge[b-1].append(a)
        connect[b-1][s[a-1]] += 1

for i in range(N):
    if connect[i]["A"] == 0 or connect[i]["B"] == 0:
        Q.append(i+1)

while Q:
    temp = Q.pop(0)
    if temp in L:
        L.remove(temp)
    for i in edge[temp-1]:
        edge[i-1].remove(temp)
        connect[i-1][s[temp-1]] -= 1
        if connect[i-1]["A"] == 0 or connect[i-1]["B"] == 0:
            Q.append(i)

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
s = input()
edge, connect = [[] for _ in range(N)], [{"A":0, "B":0} for _ in range(N)]
L, S = set(), [_ for _ in range(1, N+1)]
Nodes =set(str(_) for _ in range(1, N+1))

for _ in range(M):
    a, b = map(int, input().split())
    edge[a-1].append(b)
    connect[a-1][s[b-1]] += 1
    if a != b:
        edge[b-1].append(a)
        connect[b-1][s[a-1]] += 1
    if a in S:
        if connect[a-1]["A"] >= 1 and connect[a-1]["B"] >= 1:
            S.remove(a)
    if b in S:
        if connect[b-1]["A"] >= 1 and connect[b-1]["B"] >= 1:
            S.remove(b)

while S:
    temp = S.pop(0)
    L |= {str(temp)}
    for i in edge[temp-1]:
        edge[i-1].remove(temp)
        connect[i-1][s[temp-1]] -= 1
        if connect[i-1]["A"] == 0 or connect[i-1]["B"] == 0:
            S.append(i)

print("Yes" if Nodes - L else "No")

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
s = input()

edge, connect = [[] for i in range(N)], [set() for i in range(N)]
L, S = set(), [_ for _ in range(1, N+1)]
Nodes =set(str(_) for _ in range(1, N+1))

for _ in range(M):
    a, b = map(int, input().split())
    edge[a-1].append(b)
    connect[a-1] |= set(s[b-1])
    if a != b:
        edge[b-1].append(a)
        connect[b-1] |= set(s[a-1])
    if connect[a-1] == {"A", "B"} and a in S:
        S.remove(a)
    if connect[b-1] == {"A", "B"} and b in S:
        S.remove(b)

while S:
    temp = S.pop(0)
    L |= {str(temp)}
    for i in edge[temp-1]:
        edge[i-1].remove(temp)
        label = set()
        for j in edge[i-1]:
            label |= set(s[j-1])
        if label != {"A", "B"}:
            S.append(i)

print("Yes" if Nodes - L else "No")

Submission status: Runtime Error

Solution code:
import collections

n,m = map(int,input().split())
s = list(str(input()))
key = collection.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: Runtime Error

Solution code:
import collections

n,m = map(int,input().split())
s = list(str(input()))
key = collection.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[j][s[num]] -= 1
    if li[j]["A"] == 0 or li[j]["B"] == 0:
      if ans[j] == 0:
        key.append(j)
        ans[j] = 1

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

Submission status: Runtime Error

Solution code:

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

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


def adjAB(graph,node):
    Aflag =False
    Bflag =False
    for i in graph[node]:
        if s[i-1]=='A':
            Aflag = True
        if s[i-1]=='B':
            Bflag = True
        if Aflag and Bflag:
            break
    if Aflag and Bflag:
        return(True)
    else:
        return(False)


def deleteNode(graph,node,s):
    graph.pop(node,None)
    s[node-1]='C'
    print(s)
        


from collections import defaultdict
graphAB = defaultdict(list)

for i,j in abli:
    addEdge(graphAB,i,j)
    if i != j:
        addEdge(graphAB,j,i)


flag = True

while flag:
    flag = False
    deletelist = []
    for i in graphAB:
        if not adjAB(graphAB,i):
            deletelist.append(i)
            flag = True
    for i in deletelist:
        deleteNode(graphAB,i,s)

print(graphAB)

if graphAB == {}:
    print('No')
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000).
def have_loop(G, V):
    #Gに閉路があるかを判定 Gは隣接グラフによる表現. 0-based Vは頂点数
    status = [0] * V #0 = 未訪問　1 = 訪問中 2 = 訪問済
    def visit(n):
        if status[n] == 1:
            print('Yes')
            exit()
        elif status[n] == 0:
            status[n] = 1
            for v in G[n]:
                visit(v)
            status[n] = 2
        return None
    for v in range(V):
        visit(v)
    print('No')
    return None


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)

have_loop(G, 2 * N)

Submission status: Runtime Error

Solution code:
def have_loop(G, V):
    #Gに閉路があるかを判定 Gは隣接グラフによる表現. 0-based Vは頂点数
    status = [0] * V #0 = 未訪問　1 = 訪問中 2 = 訪問済
    def visit(n):
        if status[n] == 1:
            print('Yes')
            exit()
        elif status[n] == 0:
            status[n] = 1
            for v in G[n]:
                visit(v)
            status[n] = 2
        return None
    for v in range(V):
        visit(v)
    print('No')
    return None


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)

have_loop(G, 2 * N)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
N,M=map( int, raw_input().split() )
S=raw_input()

C=[ [0 for i in range(2) ] for j in range(N+1)  ] 	#C[i][0] A no kazu , C[i][1] B no kazu
nl=[ set() for i in range(N+1) ]
D=[ 0 for i in range(N+1) ]		#Mukouka flag   1:delete

for i in range(M):
	a,b=map(int, raw_input().split() )
	nl[a].add(b)
	nl[b].add(a)

	if a==b:
		if S[a-1]=="A": 
			C[a][0]+=1			
		elif S[a-1]=="B":
			C[a][1]+=1			
	else:
		if S[a-1]=="A": 
			C[b][0]+=1
		elif S[a-1]=="B":
			C[b][1]+=1
		if S[b-1]=="A": 
			C[a][0]+=1
		elif S[b-1]=="B":
			C[a][1]+=1


def func(i):
	print "i,C::",i,C,nl
	if D[i]==1: return
	a_cnt=C[i][0]
	b_cnt=C[i][1]

	if a_cnt==0 or b_cnt==0:
		D[i]=1	#Mukouka flag wo on
		for x in nl[i]:
			if D[x]==1: continue

			if a_cnt>0: C[x][0]-=1;C[i][0]-=1
			elif b_cnt>0: C[x][1]-=1;C[i][1]-=1
			if C[x][0]==0 or C[x][1]==0:
				func(x)


for i in range(1,N+1):
	func(i)



for i,x in enumerate(D):
	if i==0:continue
	if x==0:
		for u in nl[i]:
			if D[u]==0:
				print "Yes"
				quit()
else:
	print "No"

Submission status: Runtime Error

Solution code:
N,M=map( int, raw_input().split() )
S=raw_input()

C=[ [0 for i in range(2) ] for j in range(N+1)  ] 
nl=[ set() for i in range(N+1) ]
D=[ 0 for i in range(N+1) ]		#Mukouka flag   1:delete

for i in range(M):
	a,b=map(int, raw_input().split() )
	nl[a].add(b)
	nl[b].add(a)

	if a==b:
		if S[a-1]=="A": 
			C[a][0]+=1			
		elif S[a-1]=="B":
			C[a][1]+=1			
	else:
		if S[a-1]=="A": 
			C[b][0]+=1
		elif S[a-1]=="B":
			C[b][1]+=1
		if S[b-1]=="A": 
			C[a][0]+=1
		elif S[b-1]=="B":
			C[a][1]+=1


def func(i):
	if D[i]==1: return
	a_cnt=C[i][0]
	b_cnt=C[i][1]

	if a_cnt==0 or b_cnt==0:
		D[i]=1	#Mukouka flag wo on
		for x in nl[i]:
			if D[x]==1: continue

			if a_cnt>0: C[x][0]-=1;C[i][0]-=1
			elif b_cnt>0: C[x][1]-=1;C[i][1]-=1
			if C[x][0]==0 or C[x][1]==0:
				func(x)


for i in range(1,N+1):
	func(i)



for i,x in enumerate(D):
	if i==0:continue
	if x==0:
		for u in nl[i]:
			if D[u]==0:
				print "Yes"
				quit()
else:
	print "No"

Submission status: Runtime Error

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

g = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 1-indexed -> 0-indexed
    g[a].add(b)  # edge
    g[b].add(a)

q = [True for _ in range(n)]
left = n
i = 0
cnt_ok = 0
while left > 0:
    fa, fb = False, False
    for j in g[i]:
        if s[j] == 'A':
            fa = True
        elif s[j] == 'B':
            fb = True
        if fa and fb:
            break
    if fa and fb:
        cnt_ok += 1
        if cnt_ok == left:
            break
    else:
        s[j] = 'X'  # 除外された頂点
        q[i] = False
        left -= 1
        cnt_ok = 0
    i += 1
    if i == n:
        i = 0

print('Yes' if left > 0 else 'No')

Submission status: Runtime Error

Solution code:
N,M =  map(int, input().split())

s = input()
a = [[] for i in range(N+1)]

chstr = "AABB"

for i in range(M):
    x,y =  map(int, input().split())
    a[x-1].append(y-1)
    if x != y:
        a[y-1].append(x-1)


### print(a)

flag = False

def goToNext(startpos, currentpos, strpos):
    global flag

    if strpos % 4 == 0:
        if startpos in a[currentpos]:
            flag = True
            return

    for i in a[currentpos]:
        if chstr[strpos % 4] == s[i] and flag == False:
            goToNext(startpos, i, strpos+1)


for i in range(N):
    startpos = i
    if s[startpos] == 'B':
        continue

    goToNext(i, i, 1)

if flag == False:
    print('No')
else:
    print('Yes')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
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)
 
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)
 
def erase(v):
  if s[v] == "A":
    l = 0
  else:
    l = 1
  for q in links[v][0]:
    if not able[q]:
      continue
    links[q][l].remove(v)
    if links[q][l] == set():
      able[q] = False
      erase(q)
  for q in links[v][1]:
    if not able[q]:
      continue
    links[q][l].remove(v)
    if links[q][l] == set():
      able[q] = False
      erase(q)

for i in range(n):
  if not able[i]:
    erase(i)
if any(able):
  print("Yes")
else:
  print("No")

Submission status: Runtime Error

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

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)
flag = 1
tmp = set()
for i in range(n):
  if able[i]:
    tmp.add(i)
while flag ==1:
  flag = 0
  for i in tmp:
    if not able[i]:
      continue
    for k in range(2):
      for j in links[i][k].copy():
        if not able[j]:
          links[i][k].remove(j)
    if (links[i][0] == set() or links[i][1] == set()):
      flag =1
      tmp.remove(i)
      able[i] = False
if any(able):
  print("Yes")
else:
  print("No")

Submission status: Runtime Error

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,input().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):
    # gori~~~
    if time.time() - start_time > 1.8:
        break
    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: Runtime Error

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict
sys.setrecursionlimit(10**7)

s = input().strip()
ds = [defaultdict(set), defaultdict(set)]
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    x = 0 if s[i] == s[j] else 1
    y = 1 if s[i] == s[j] else 0
    ds[x][str(x) + str(i)].add(str(y) + str(j))
    ds[x][str(x) + str(j)].add(str(y) + str(i))


checked = set()

path = set()

def walk(i, depth):
    dd = ds[depth]
    checked.add(i)
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if item in path:
            return True
        if item not in checked:
            path.add(item)
            r = r or walk(item, (depth+1) % 2)
            path.remove(item)
    return r

for item in ds[0]:
    if item not in checked:
        path.add(item)
        if walk(item, 0):
            print('Yes')
            break
        path.remove(item)
else:
    print('No')

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(200000)


def close(v, i):
    j = int(s[v] == 'B')
    for u in links[v][i].copy():
        links[u][j].remove(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 _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    la, lb = links[a], links[b]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)
    i, j = [(0, 1), (1, 0)][s[a] == 'B']
    if not lb[i] and lb[j]:
        able[b] = True
    lb[i].add(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: Runtime Error

Solution code:
def close(v, i):
    j = int(s[v] == 'B')
    for u in links[v][i].copy():
        links[u][j].remove(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 _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    la, lb = links[a], links[b]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)
    i, j = [(0, 1), (1, 0)][s[a] == 'B']
    if not lb[i] and lb[j]:
        able[b] = True
    lb[i].add(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: Runtime Error

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict

s = input().strip()
d = {}
starts = set()
for s1 in 'AB':
    d[s1] = {}
    for s2 in 'AB':
        d[s1][s2] = defaultdict(set)
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    d[s[i]][s[j]][i].add(j)
    d[s[j]][s[i]][j].add(i)
    if s[i] == 'A' and s[j] == 'A':
        starts.add(i)


checked = set()
def walk(i, depth, path):
    if depth == 0:
        dd = d['A']['A']
    elif depth == 1:
        dd = d['A']['B']
    elif depth == 2:
        dd = d['B']['B']
    else:
        dd = d['B']['A']
    checked.add(((depth)%4, i))
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if ((depth+1)%4, item) in path:
            return True
        if ((depth+1)%4, item) not in checked:
#            r = r or walk(item, (depth+1) % 4, path + [((depth+1)%4 ,item)])
            r = r or walk(item, (depth+1) % 4, path | {((depth+1)%4 ,item)})
    return r

result = False
for item in starts:
    if item not in checked:
        result = result or walk(item, 0, {(0, item)})
#        result = result or walk(item, 0, [(0, item)])
if result:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split(' ')]
import sys
from collections import defaultdict

s = input().strip()
d = {}
starts = set()
for s1 in 'AB':
    d[s1] = {}
    for s2 in 'AB':
        d[s1][s2] = defaultdict(set)
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    d[s[i]][s[j]][i].add(j)
    d[s[j]][s[i]][j].add(i)
    if s[i] == 'A' and s[j] == 'A':
        starts.add(i)


checked = set()
def walk(i, depth, path):
    if depth == 0:
        dd = d['A']['A']
    elif depth == 1:
        dd = d['A']['B']
    elif depth == 2:
        dd = d['B']['B']
    else:
        dd = d['B']['A']
    checked.add(((depth+1)%4, i))
    if len(dd[i]) == 0:
        return False
    r = False
    for item in dd[i]:
        if ((depth+1)%4, item) in path:
            return True
        if ((depth+1)%4, item) not in checked:
#            r = r or walk(item, (depth+1) % 4, path + [((depth+1)%4 ,item)])
            r = r or walk(item, (depth+1) % 4, path | {((depth+1)%4 ,item)})
    return r

result = False
for item in starts:
    if item not in checked:
        result = result or walk(item, 0, {(0, item)})
#        result = result or walk(item, 0, [(0, item)])
if result:
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

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

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

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


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

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


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

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

print('No')

Submission status: Runtime Error

Solution code:
# C
from collections import deque

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

# 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 = degue()
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] == "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")