Problem: Ken loves _ken-ken-pa_ (Japanese version of hopscotch). Today, he will play it on a directed graph G. G consists of N vertices numbered 1 to N, and M edges. The i-th edge points from Vertex u_i to Vertex v_i.  First, Ken stands on Vertex S. He wants to reach Vertex T by repeating ken- ken-pa. In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.  Determine if he can reach Vertex T by repeating ken-ken-pa. If the answer is yes, find the minimum number of ken-ken-pa needed to reach Vertex T. Note that visiting Vertex T in the middle of a ken-ken-pa does not count as reaching Vertex T by repeating ken-ken-pa.

Submission attempts (in order):
def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i in visited:
            continue
        visited.add(i)
        a = []
        for j in e[i]:
            a += e[j]
        b = []
        for j in a:
            b += e[j]
        b = set(b)
        if t in b:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(b)]
        return -1


print(BC132_E())

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)

    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1

    f = []
    for i in range(n):
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        f.append(b)
    return -1

    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        if t in f[i]:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(f[i])]
    return -1


print(BC132_E())


def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i in visited:
            continue
        visited.add(i)
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        if t in b:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(b)]
        return -1


print(BC132_E())

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    f = []
    for i in range(n):
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(b):
            b.update(e[j])
        f.append(b)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        if t in f[i]:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(f[i])]
    return -1


print(BC132_E())

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        if t in b:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(b)]
        return -1


print(BC132_E())

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    a, b = set(), set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        v = set()
        for j in e[i]:
            if j in a: continue
            a.add(j)
            for k in e[j]:
                if k in b: continue
                b.add(k)
                v.update(e[k])
        if t in v:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(v)]
    return -1


print(BC132_E())

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted