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:
import os
import sys

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

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


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

diffs = [set() for _ in range(N)]
sames = [set() for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    if S[a] == S[b]:
        sames[a].add(b)
        sames[b].add(a)
    else:
        diffs[a].add(b)
        diffs[b].add(a)
diffs = [list(s) for s in diffs]
sames = [list(s) for s in sames]

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


# @debug
def dfs(v, pc=None, seen=None):
    seen = seen or set()

    if v in seen:
        return True
    seen.add(v)
    if pc is not None:
        checked[int(pc == 'A')][v] = True

    if pc is None or pc == S[v]:
        ok = False
        for u in diffs[v]:
            if not checked[int(S[v] == 'A')][u] and dfs(u, S[v], seen):
                ok = True
                break
        if not ok:
            seen.remove(v)
            return False

    if pc is None or pc != S[v]:
        ok = False
        for u in sames[v]:
            if not checked[int(S[v] == 'A')][u] and dfs(u, S[v], seen):
                ok = True
                break
        if not ok:
            seen.remove(v)
            return False
    return True


ok = False
for v in range(N):
    if dfs(v):
        ok = True
        break
if ok:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
import os
import sys

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

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


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 = [set() for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)

checked = [False] * N


# @debug
def dfs(v, pc=None, seen=None):
    seen = seen or set()

    if v in seen:
        return True
    seen.add(v)
    checked[v] = True

    if pc is None or pc == S[v]:
        ok = False
        for u in graph[v]:
            if S[u] != S[v]:
                if dfs(u, S[v], seen):
                    ok = True
                    break
        if not ok:
            seen.remove(v)
            return False

    if pc is None or pc != S[v]:
        ok = False
        for u in graph[v]:
            if S[u] == S[v]:
                if dfs(u, S[v], seen):
                    ok = True
                    break
        if not ok:
            seen.remove(v)
            return False
    return True


ok = False
for v in range(N):
    if not checked[v] and dfs(v):
        ok = True
        break
if ok:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
#ライブラリインポート
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)
	#print(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()
		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"
	#print(check)
	for i in range(N):
		if check[i] == "Yes":
			judge = "Yes"
	print(judge)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

# 頂点iがラベルA・Bの頂点といくつ隣接しているか
connect_label = [[0, 0] for i in range(N)]

# 削除する予定の頂点を管理するキュー
queue = deque()

# 削除済みの頂点を管理する集合
deleted_set = set()

# 各頂点の連結情報
G = [[] for i in range(N)]

# 辺の情報を入力
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
    connect_label[a][1 - (S[b] == "A")] += 1
    connect_label[b][1 - (S[a] == "A")] += 1

# AまたはBのみとしか連結してないものをキューに追加
for i in range(N):
    if 0 in connect_label[i]:
        queue.append(i)

# キューが空になるまで削除を繰り返す
while queue:
    n = queue.pop()
    deleted_set.add(n)

    # 連結していた頂点について情報を書き換える
    for v in G[n]:
        connect_label[v][1 - (S[n] == "A")] -= 1
        # 未削除で、AまたはBのみとしか連結しなくなったものはキューに追加
        if (v not in deleted_set) and (0 in connect_label[v]):
            queue.appendleft(v)

# 全て削除していたらNo, そうでなければYes
print("Yes" if len(deleted_set) != N else "No")

Submission status: Wrong Answer

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)]
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]:
        graphABopp[j].remove(i)
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
            #print(visitset,'add')
    for j in graphABopp[i]:
        graphAB[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: Wrong Answer

Solution code:

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


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)

connodes = set()
for i,j in edges:
    ii = min(i,j)
    jj = max(i,j)
    addEdge(graphAB,ii,jj)
    addEdge(graphABopp,jj,ii)
    if i != j:
        connodes.add(i)
        connodes.add(j)



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)



visitlist = [i for i in connodes if not adjAB(i)]
#print(visitset)

while bool(visitlist):
    i = visitlist.pop()
    for j in graphAB[i]:
        graphABopp[j].remove(i)
        if not adjAB(j):
            visitlist.append(j)
            #print(visitset,'add')
    for j in graphABopp[i]:
        graphAB[j].remove(i)
        if not adjAB(j):
            visitlist.append(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: Wrong Answer

Solution code:

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


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


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)

for i,j in edgeset:
    addEdge(graphAB,i,j)
    addEdge(graphABopp,j,i)

abli = [[0,0] for i in range(n)]

def incrimentAB(j,char):
    if char == 'A':
        abli[j-1][0] += 1
    if char =='B':
        abli[j-1][1] += 1

def decrimentAB(j,char):
    if char == 'A':
        abli[j-1][0] -= 1
    if char =='B':
        abli[j-1][1] -= 1


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

for i,j in edgeset:
    incrimentAB(j,s[i-1])
    incrimentAB(i,s[j-1])



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

while bool(visitset):
    i = visitset.pop()
    deleteset.add(i)
    for j in graphAB[i]:
        decrimentAB(j,s[i-1])
        graphABopp[j].remove(i)
        if not adjAB(j):
            visitset.add(j)
            print(visitset,'add')
    for j in graphABopp[i]:
        decrimentAB(j,s[i-1])
        graphAB[j].remove(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: Wrong Answer

Solution code:
import queue
import sys


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):
            print(j)
            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: Wrong Answer

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] is 'A':
            toa = True
            if tob:
                return True
        elif s[k - 1] is '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 len(node) == 0:
    print('No')
else:
    print('Yes')

Submission status: Wrong Answer

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):
    graph.pop(node,None)
    s[node-1] = 'C'
        


from collections import defaultdict
graphAB = defaultdict(list)

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


visitset = set(graphAB.keys())
deleteset=set()

while bool(visitset):
    i = visitset.pop()
    print(i,visitset)
    if not adjAB(graphAB,i):
        deleteset.add(i)
        print(i)
        tmp = set(graphAB[i])
        visitset = (visitset | tmp) - deleteset
        deleteNode(graphAB,i)




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

Submission status: Wrong Answer

Solution code:

n,m = map(int,input().split())
s = 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):
    graph.pop(node,None)
    for i in graph:
        for j in (j for j,x in enumerate(graph[i]) if graph[i] == node):
            del graph[i][j]


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)


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

Submission status: Wrong Answer

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 "Yes"
else:
	print "No"

Submission status: Wrong Answer

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: Wrong Answer

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
        else:
            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: Wrong Answer

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:
        if startpos in a[currentpos]:
            flag = True
            return
        else:
            return

    for i in a[currentpos]:
        if chstr[strpos] == 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: Wrong Answer

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 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: Wrong Answer

Solution code:
#from collections import deque
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([])
L = []

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[m] == '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: Wrong Answer

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

class Node:
    def __init__(self, node_id, label):
        self.node_id = node_id
        self.label = label
        self.from_links = set()
        self.to_links = set()
    def from_link(self, l):
        self.from_links.add(l)
    def to_link(self, l):
        self.to_links.add(l)
    def remove_from_link(self, l):
        self.from_links.remove(l)
    def remove_to_link(self, l):
        self.to_links.remove(l)
    def is_orphen(self):
        return not (self.to_links or self.from_links)
    def __repr__(self):
        return "Node<%d, %s>" % (self.node_id, label)

class Link:
    def __init__(self, frm, to):
        self.frm = frm
        self.to = to
        self.to_node = None
        self.frm_node = None
    def __repr__(self):
        return "Link<%s, %s>" % (self.frm_node, self.to_node)

class Graph:
    def __init__(self):
        self.nodes = dict()
        self.links = set()
    def add_node(self, node):
        self.nodes[node.node_id] = node
    def add_link(self, l):
        self.links.add(l)
        l.to_node = self.nodes[l.to]
        l.frm_node = self.nodes[l.frm]
        self.nodes[l.frm].from_link(l)
        self.nodes[l.to].to_link(l)
    def remove_link(self, l):
        self.links.remove(l)
        
        fn = self.nodes[l.frm]
        tn = self.nodes[l.to]
        fn.remove_from_link(l)
        tn.remove_to_link(l)
    def remove_node(self, n):
        del self.nodes[n.node_id]

g = Graph()
for i,label in enumerate(s,1):
    g.add_node(Node(i, label))
for _ in range(M):
    a,b = map(int, input().split())
    g.add_link(Link(a, b))
    g.add_link(Link(b, a))

while True:
    flag = False
    touched = set()
    for n in g.nodes.values():
        if not n.to_links: continue
        lbl = set(m.to_node.label for m in n.from_links)
        if 'A' not in lbl or 'B' not in lbl:
            touched.add(n)
            for l in n.to_links.copy():
                g.remove_link(l)
                touched.add(l.frm_node)
                touched.add(l.to_node)
    if touched:
        for n in touched:
            if n.is_orphen():
                g.remove_node(n)
    else:
        break
print('Yes' if g.nodes else 'No')

Submission status: Wrong Answer

Solution code:
print("Yes")

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split(' '))
s = input()

p = {0:[]}
for i in range(0,N+1):
    p.update({i:[]})


for i in range(M):
    a, b = (int(j) for j in input().split(' '))
    p[a].append(b)
    p[b].append(a)

ab_s =''
ans = 'Yes'
for a in range(1, N+1):
    for i in p[a]:
        ab_s += s[i-1]
    
    if 'A' in list(ab_s) and 'B' in list(ab_s):
        pass
    else:
        ans = 'No'

    ab_s = ''

print(ans)

Submission status: Wrong Answer

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(b)
        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(a)
        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: Wrong Answer

Solution code:
import numpy as np
def main():
    N, M = map(int, input().split())
    S = list(input())
    g = np.zeros((N, 2))
    for m in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if S[b] == 'A':
            g[a][0] = 1
        else:
            g[a][1] = 1
        if S[a] == 'A':
            g[b][0] = 1
        else:
            g[b][1] = 1
    for point in g:
        if point[point == 0].size > 0:
            print('No')
            return 0
    print('Yes')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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]:
            remove(b)
            if i in ba[b]:
                ba[b].remove(i)
        ab[i] = set()
    else:
        if bb[i]: return
        for a in ba[i]:
            remove(a)
            if i in ab[a]:
                ab[a].remove(i)
        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')