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

Solution code:
def have_loop(G, V):
    #Gに閉路があるかを判定 Gは隣接グラフによる表現. 0-based Vは頂点数
    parent = [{v} for v in range(V)] #各頂点の親集合
    reached = [False] * V
    for v in range(V):
        stack = []
        if not reached[v]:
            stack.append(v)
            while stack:
                u = stack.pop()
                reached[u] = True
                for w in G[u]:
                    if w in parent[u]:
                        return True
                    elif not reached[w]:
                        parent[w] |= parent[u]
                        stack.append(w)
    return False

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)
if have_loop(G, 2 * N):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
def have_loop(G, V):
    #Gに閉路があるかを判定 Gは隣接グラフによる表現. 0-based Vは頂点数
    parent = [{v} for v in range(V)] #各頂点の親集合
    reached = [False] * V
    for v in range(V):
        stack = []
        if not reached[v]:
            stack.append(v)
            while stack:
                u = stack.pop()
                reached[u] = True
                for w in G[u]:
                    if w in parent[u]:
                        return True
                    elif not reached[w]:
                        parent[w] |= parent[u]
                        stack.append(w)
    return False

N, M = map(int, input().split())
s = input()
G = [[] for _ in range(4 * 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)
if have_loop(G, 4 * N):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()
nodes = [i for i in range(N)]
del_nodes = []
ABnumbers = [[0,0] for _ in range(N)]
outs = [[] for _ in range(N)]
for _ in range(M):
    edge = [int(j)-1 for j in input().split()]
    i = edge[0]
    j = edge[1]
    if i == j:
        outs[i].append(i)
        if s[i] == "A":
            ABnumbers[i][0] += 1
        else:
            ABnumbers[i][1] += 1
    else:
        if s[i] == "A":
            ABnumbers[j][0] += 1
        else:
            ABnumbers[j][1] += 1
        if s[j] == "A":
            ABnumbers[i][0] += 1
        else:
            ABnumbers[i][1] += 1
        outs[i].append(j)
        outs[j].append(i)
for i in range(N):
    if 0 in ABnumbers[i]:
        del_nodes.append(i)
while del_nodes != []:
    i = del_nodes[0]
    nodes.remove(i)
    del_nodes.remove(i)
    for j in outs[i]:
        if i != j:
            outs[j].remove(i)
            if s[i] == "A":
                ABnumbers[j][0] -= 1
            else:
                ABnumbers[j][1] -= 1
            if 0 in ABnumbers[j]:
                sets = set(del_nodes)
                sets.add(j)
                del_nodes = list(sets)
if nodes==[]:
    print ("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()
nodes = [i for i in range(N)]
del_nodes = []
ABnumbers = [[0,0] for _ in range(N)]
outs = [[] for _ in range(N)]
for _ in range(M):
    edge = [int(j)-1 for j in input().split()]
    i = edge[0]
    j = edge[1]
    if i == j:
        outs[i].append(i)
        if s[i] == "A":
            ABnumbers[i][0] += 1
        else:
            ABnumbers[i][1] += 1
    else:
        if s[i] == "A":
            ABnumbers[j][0] += 1
        else:
            ABnumbers[j][1] += 1
        if s[j] == "A":
            ABnumbers[i][0] += 1
        else:
            ABnumbers[i][1] += 1
        outs[i].append(j)
        outs[j].append(i)
for i in range(N):
    if 0 in ABnumbers[i]:
        del_nodes.append(i)
for i in del_nodes:
    nodes.remove(i)
    for j in outs[i]:
        if i != j:
            outs[j].remove(i)
            if s[i] == "A":
                ABnumbers[j][0] -= 1
            else:
                ABnumbers[j][1] -= 1
            if 0 in ABnumbers[j] and j not in del_nodes:
                del_nodes.append(j)
if nodes==[]:
    print ("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

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)
 
n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [None] * 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] = None
      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] = None
      erase(q)  
for i in range(n):
  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
    able[i] = None
    erase(i)
if any(able):
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

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 = [None] * 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)

used = [None]*n
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
      used[q] = True
      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
      used[q] = True
      erase(q)

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

Submission status: Time Limit Exceeded

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)

used = [False]*n
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
      used[q] = True
      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
      used[q] = True
      erase(q)

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

Submission status: Time Limit Exceeded

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]:
    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
    able[i] = False
    erase(i)
if any(able):
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

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]:
    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
    able[i] = False
    erase(i)
if any(able):
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

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.copy():
    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: Time Limit Exceeded

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

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

chstr = "AABB"

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

### print(a)

flag = False

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

    if strpos == 4:
        if a[startpos][currentpos] == 1:
            flag = True
            return
        else:
            return

    for i in range(N):
        if a[currentpos][i] == 1 and 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: Time Limit Exceeded

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
while flag ==1:
  flag = 0
  for i in range(n):
    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
      able[i] = False
if any(able):
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False]
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
l = [set() for i in range(n+1)]
for pi in p: 
    l[pi[0]].add(pi[1])
    l[pi[1]].add(pi[0])

while True:
  ans = able.count(True)
  able = [False]*(n+1)
  for i in range(1,n+1):
    ab = 0
    for j in l[i]:
      if s[j-1] == "A":
        ab |= 1
      else:
        ab |= 2
      if ab == 3:
        able[i] = True
        break
  for i in range(1,n+1):
    for j in l[i].copy():
      if not able[j]:
        l[i].remove(j)
  tmp = able.count(True)
  if ans == tmp:
    break
if any(able):
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()
edges = []
nodes = [i for i in range(N)]
for i in range(M):
    edges.append([int(j)-1 for j in input().split()])
del_nodes = []
ABnumbers = []
for i in range(N):
    ABnumbers.append([0,0])
for edge in edges:
    i = edge[0]
    j = edge[1]
    if i == j:
        if s[i] == "A":
            ABnumbers[i][0] += 1
        else:
            ABnumbers[i][1] += 1
    else:
        if s[i] == "A":
            ABnumbers[j][0] += 1
        else:
            ABnumbers[j][1] += 1
        if s[j] == "A":
            ABnumbers[i][0] += 1
        else:
            ABnumbers[i][1] += 1
for i in range(N):
    if 0 in ABnumbers[i]:
        del_nodes.append(i)
for i in del_nodes:
    nodes.remove(i)
    edges_copy = edges[:]
    for edge in edges:
        if i in edge:
            edges_copy.remove(edge)
            if edge[0] != edge[1]:
                if edge[0] == i:
                    j = edge[1]
                else:
                    j = edge[0]
                if s[i] == "A":
                    ABnumbers[j][0] -= 1
                else:
                    ABnumbers[j][1] -= 1
                if 0 in ABnumbers[j] and j not in del_nodes:
                    del_nodes.append(j)
    edges = edges_copy[:]
if nodes==[]:
    print ("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()
edges = []
nodes = [i for i in range(N)]
for i in range(M):
    edges.append([int(j)-1 for j in input().split()])
del_nodes = []
ABnumbers = []
for i in range(N):
    ABnumbers.append([0,0])
for edge in edges:
    i = edge[0]
    j = edge[1]
    if i == j:
        if s[i] == "A":
            ABnumbers[i][0] += 1
        else:
            ABnumbers[i][1] += 1
    else:
        if s[i] == "A":
            ABnumbers[j][0] += 1
        else:
            ABnumbers[j][1] += 1
        if s[j] == "A":
            ABnumbers[i][0] += 1
        else:
            ABnumbers[i][1] += 1
for i in range(N):
    if 0 in ABnumbers[i]:
        del_nodes.append(i)
for i in del_nodes:
    nodes.remove(i)
    del_edges = []
    for edge in edges:
        if i in edge:
            del_edges.append(edge)
            if edge[0] != edge[1]:
                if edge[0] == i:
                    j = edge[1]
                else:
                    j = edge[0]
                if s[i] == "A":
                    ABnumbers[j][0] -= 1
                else:
                    ABnumbers[j][1] -= 1
                if 0 in ABnumbers[j] and j not in del_nodes:
                    del_nodes.append(j)
    for edge in del_edges:
        edges.remove(edge)
if nodes==[]:
    print ("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()
edges = []
nodes = [i for i in range(N)]
for i in range(M):
    edges.append([int(j)-1 for j in input().split()])
del_nodes = []
ABnumbers = []
for i in nodes:
    A_count = 0
    B_count = 0
    for edge in edges:
        if edge[0] == i:
            if s[edge[1]] == "A":
                A_count += 1
            else:
                B_count += 1
        elif edge[1] == i:
            if s[edge[0]] == "A":
                A_count += 1
            else:
                B_count += 1
    ABnumbers.append([A_count, B_count])
    if 0 in [A_count, B_count]:
        del_nodes.append(i)
for i in del_nodes:
    nodes.remove(i)
    del_edges = []
    for edge in edges:
        if i in edge:
            del_edges.append(edge)
            if edge[0] != edge[1]:
                if edge[0] == i:
                    j = edge[1]
                else:
                    j = edge[0]
                if s[i] == "A":
                    ABnumbers[j][0] -= 1
                else:
                    ABnumbers[j][1] -= 1
                if 0 in ABnumbers[j] and j not in del_nodes:
                    del_nodes.append(j)
    for edge in del_edges:
        edges.remove(edge)
if nodes==[]:
    print ("No")
else:
    print("Yes")

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()
edges = []
nodes = [i for i in range(N)]
for i in range(M):
    edges.append([int(j)-1 for j in input().split()])
while True:
    for i in nodes:
        A_count = False
        B_count = False
        for edge in edges:
            if edge[0] == i:
                if s[edge[1]] == "A":
                    A_count = True
                else:
                    B_count = True
            if edge[1] == i:
                if s[edge[0]] == "A":
                    A_count = True
                else:
                    B_count = True
        if A_count and B_count:
                continue
        else:
            nodes.remove(i)
            del_list = []
            for edge in edges:
                if i in edge:
                    del_list.append(edge)
            for edge in del_list:
                edges.remove(edge)
            break
    else:
        if nodes==[]:
            print ("No")
        else:
            print("Yes")
        break

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()
edges = []
nodes = N*[True]
for i in range(M):
    edges.append([int(j)-1 for j in input().split()])
while True:
    for i in range(N):
        if nodes[i]:
            A_count = False
            B_count = False
            for edge in edges:
                if edge[0] == i:
                    if s[edge[1]] == "A":
                        A_count = True
                    else:
                        B_count = True
                if edge[1] == i:
                    if s[edge[0]] == "A":
                        A_count = True
                    else:
                        B_count = True
            if A_count and B_count:
                continue
            else:
                nodes[i] = False
                del_list = []
                for edge in edges:
                    if i in edge:
                        del_list.append(edge)
                for edge in del_list:
                    edges.remove(edge)
                break
    else:
        if True in nodes:
            print ("Yes")
        else:
            print("No")
        break

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
s = input()
edges = []
nodes = N*[True]
for i in range(M):
    edges.append([int(j)-1 for j in input().split()])
while True:
    for i in range(N):
        if nodes[i]:
            A_count = False
            B_count = False
            for edge in edges:
                if edge[0] == i and nodes[edge[1]]:
                    if s[edge[1]] == "A":
                        A_count = True
                    else:
                        B_count = True
                if edge[1] == i and nodes[edge[0]]:
                    if s[edge[0]] == "A":
                        A_count = True
                    else:
                        B_count = True
            if A_count and B_count:
                continue
            else:
                nodes[i] = False
                break
    else:
        if True in nodes:
            print ("Yes")
        else:
            print("No")
        break

Submission status: Time Limit Exceeded

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.6:
        return # gori~~~
    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: Time Limit Exceeded

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.7:
        return # gori~~~
    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: Time Limit Exceeded

Solution code:
import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [list(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):
    if time.time() - start_time > 1.7:
        return # gori~~~
    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: Time Limit Exceeded

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):
    if time.time() - start_time > 1.7:
        return # gori~~~
    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: Time Limit Exceeded

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):
    if time.time() - start_time > 1.8:
        return # gori~~~
    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: Time Limit Exceeded

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):
    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)
    # gori~~~
    if time.time() - start_time > 1.8:
        break
print('No')

Submission status: Time Limit Exceeded

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):
    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)
    # gori~~~
    if time.time() - start_time > 1.9:
        break
print('No')

Submission status: Time Limit Exceeded

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

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

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 i not in dd:
        return False
    for item in dd[i]:
        if item in path:
            return True
        if item not in checked:
            path.add(item)
            if walk(item, (depth+1) % 2):
                return True
            path.remove(item)
    return False

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

Submission status: Time Limit Exceeded

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)]
starts = set()
for ll in sys.stdin:
    i, j = ll.strip().split(' ')
    i, j = int(i)-1, int(j)-1
    ds[0 if s[i] == s[j] else 1][str(0 if s[i] == s[j] else 1) + str(i)].add(str(1 if s[i] == s[j] else 0) + str(j))
    ds[0 if s[i] == s[j] else 1][str(0 if s[i] == s[j] else 1) + str(j)].add(str(1 if s[i] == s[j] else 0) + str(i))
    if s[i] == 'A' and s[j] == 'A':
        starts.add(str(0)+str(i))


checked = set()

path = set()
#path = []

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

result = False
for item in starts:
    if item not in checked:
        path.add(item)
        result = result or walk(item, 0)
        if result:
            print('Yes')
            break
        path.remove(item)
else:
    print('No')