Problem p03256 (python)

Fixed submission:
import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        # gori~~~
        print('No')
        exit()
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')

Buggy submission (verdict: Runtime Error):
import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    # gori~~~
    if time.time() - start_time > 1.8:
        break
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')

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

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

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


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

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


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

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

print('No')