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: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = list(input())
connect = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)
def reach(xs):
    ret = set()
    for x in xs:
        ret.add(s[x])
    return ret
update = True
while update:
    update = False
    for i in range(n):
        if s[i] != 'X':
            c = reach(connect[i])
            if not ('A' in c and 'B' in c):
                update = True
                s[i] = 'X'
if 'A' in s and 'B' in s: print('Yes')
else: print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
N, M = map(int, readline().split())
AB = "AB".index
*S, = map(AB, readline().strip())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

T = [0, 0, 1, 1]
used = [[0]*4 for i in range(N)]
for i in range(N):
    if S[i]:
        used[i][0:2] = -1,-1
    else:
        used[i][2:4] = -1,-1
def dfs(v, k):
    used[v][k] = lb
    k1 = (k + 1) % 4
    for w in G[v]:
        u = used[w][k1]
        if u == -1:
            continue
        if u or dfs(w, k1):
            return 1
    used[v][k] = -1
    return 0
for i in range(N):
    lb = i+1
    if dfs(i, 0) if S[i] == 0 else dfs(i, 2):
        sys.stdout.write("Yes\n")
        break
else:
    sys.stdout.write("No\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
N, M = map(int, readline().split())
AB = "AB".index
*S, = map(AB, readline().strip())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

T = [0, 0, 1, 1]
used = [[0]*4 for i in range(N)]
def dfs(v, k):
    if used[v][k]:
        return used[v][k] == lb
    used[v][k] = lb
    k1 = (k + 1) % 4
    nxt = T[k1]
    for w in G[v]:
        if S[w] == nxt and dfs(w, k1):
            return 1
    used[v][k] = -1
    return 0
for i in range(N):
    lb = i+1
    if dfs(i, 0) if S[i] == 0 else dfs(i, 2):
        sys.stdout.write("Yes\n")
        break
else:
    sys.stdout.write("No\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
AB = "AB".index
*S, = map(AB, input())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

T = [0, 0, 1, 1]
used = [[0]*4 for i in range(N)]
def dfs(v, k):
    if used[v][k]:
        return used[v][k] == lb
    used[v][k] = lb
    k1 = (k + 1) % 4
    nxt = T[k1]
    for w in G[v]:
        if S[w] == nxt and dfs(w, k1):
            return 1
    used[v][k] = -1
    return 0
for i in range(N):
    lb = i+1
    if dfs(i, 0) if S[i] == 0 else dfs(i, 2):
        print("Yes")
        break
else:
    print("No")

Submission status: Time Limit Exceeded

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]:
        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):
            graphAB[j].remove(i)
            decrementAB(j,i)
        else:
            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: Time Limit Exceeded

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]:
        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: Time Limit Exceeded

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 = [True] * N, [_ 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 in Q:
        if connect[a-1]["A"] and connect[a-1]["B"]:
            Q.remove(a)
    if a != b:
        edge[b-1].append(a)
        connect[b-1][s[a-1]] += 1
        if b in Q:
            if connect[b-1]["A"] and connect[b-1]["B"]:
                Q.remove(b)

count = 0
while Q:
    temp = Q.pop(0)
    if L[temp-1]:
        count += 1
        L[temp-1] = False
        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("No" if count == N else "Yes")

Submission status: Time Limit Exceeded

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 = [True for _ in range(N)], []

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)

count = 0
while Q:
    temp = Q.pop(0)
    count += 1
    L[temp-1] = False
    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:
            if L[i-1] and i not in Q:
                Q.append(i)

print("No" if count == N else "Yes")

Submission status: Time Limit Exceeded

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 = [1 for _ in range(N)], []

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 L[temp-1] == 1:
        L[temp-1] = 0
        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:
                if L[i-1] == 1 and i not in Q:
                    Q.append(i)

print("No" if L == [0 for _ in range(N)] else "Yes")

Submission status: Time Limit Exceeded

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 = [1 for _ in range(N)], []

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 L[temp-1] == 1:
        L[temp-1] = 0
        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("No" if L == [0 for _ in range(N)] else "Yes")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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 L[temp-1]:
        L[temp-1] = 0
        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.any() else "No")

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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)



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 range(1,n+1) 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: Time Limit Exceeded

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)



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 set(graphAB.keys())|set(graphABopp.keys()) 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: Time Limit Exceeded

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)



def adjAB(node):
    Aflag = False
    Bflag = False
    for i in graphAB[node]:
        if s[i-1] == 'A':
            Aflag = True
        if s[i-1] == 'B':
            Bflag = True
        if Aflag and Bflag:
            break
    for i in graphABopp[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)



visitlist = [i for i in set(graphAB.keys())|set(graphABopp.keys()) 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: Time Limit Exceeded

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)



def adjAB(node):
    Aflag = False
    Bflag = False
    for i in graphAB[node]:
        if s[i-1] == 'A':
            Aflag = True
        if s[i-1] == 'B':
            Bflag = True
        if Aflag and Bflag:
            break
    for i in graphABopp[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)



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

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: Time Limit Exceeded

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 = defaultdict(set)
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].add(b+N)
        lines[b].add(a+N)
    else:
        lines[a+N].add(b)
        lines[b+N].add(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: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,M = inpl()
s = list(input())

'''
A
1 ~ N -> mod0
N+1 ~ 2N -> mod1

B
1 ~ N -> mod2
N+1 ~ 2N -> mod3
'''

lines = defaultdict(set)
for _ in range(M):
    a,b = inpl()
    a-=1
    b-=1
    sa, sb = s[a], s[b]
    if sa == sb:
        lines[a].add(b+N)
        lines[b].add(a+N)
    else:
        lines[a+N].add(b)
        lines[b+N].add(a)

ed = [0]*(2*N)
ans = False

def dfs(s):
    global ed
    if ed[s] == 1: #今訪れている
        print('Yes')
        sys.exit()
    elif ed[s] == 2: #昔訪れた
        return
    else: #まだ
        ed[s] = 1
        for t in lines[s]:
            dfs(t)
        ed[s] = 2

tmp = 0
for s in range(N):
    if ed[s] == 0:
        dfs(s)

print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,M = inpl()
s = list(input())

'''
A
1 ~ N -> mod0
N+1 ~ 2N -> mod1

B
1 ~ N -> mod2
N+1 ~ 2N -> mod3
'''

lines = defaultdict(set)
for _ in range(M):
    a,b = inpl()
    a-=1
    b-=1
    sa, sb = s[a], s[b]
    if sa == sb:
        lines[a].add(b+N)
        lines[b].add(a+N)
    else:
        lines[a+N].add(b)
        lines[b+N].add(a)

ed = [0]*(2*N)
ans = False

def dfs(s):
    global ed
    if ed[s] == 1: #今訪れている
        print('Yes')
        sys.exit()
    elif ed[s] == 2: #昔訪れた
        return
    else: #まだ
        ed[s] = 1
        for t in lines[s]:
            dfs(t)
        ed[s] = 2

tmp = 0
for s in range(2*N):
    if ed[s] == 0:
        dfs(s)

print('No')

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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)
    for i in graphAB:
        while node in graph[i]:
            graph[i].remove(node)
        


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

while bool(visitset):
    i = visitset.pop()
    #print(i,visitset)
    if not adjAB(graphAB,i):
        #print(i)
        tmp = set(graphAB[i])
        if i in tmp:
            tmp.remove(i)
        visitset = visitset | tmp
        deleteNode(graphAB,i)




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

Submission status: Time Limit Exceeded

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:
        while node in graph[i]:
            graph[i].remove(node)


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: Time Limit Exceeded

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):
    tmp =list(map(lambda x:s[x-1],graph[node]))
    return('A' in tmp and 'B' in tmp)

def deleteNode(graph,node):
    graph.pop(node,None)
    for i in graph:
        while node in graph[i]:
            graph[i].remove(node)


from collections import defaultdict
graphAB = defaultdict(list)

for i,j in abli:
    addEdge(graphAB,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: Time Limit Exceeded

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
    return None

for v in range(2 * N):
    dfs(v)
print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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, sys.stdin.readline().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


def delete(x):
	if deleted[x]==1: return
	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:
				delete(u)


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


				

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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


def delete(x):
	if deleted[x]==1: return
	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:
				delete(u)


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


				

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