Problem:


Score : 500 points

Problem Statement

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.

Constraints

2 \leq N \leq 10^5

0 \leq M \leq \min(10^5, N (N-1))

1 \leq u_i, v_i \leq N(1 \leq i \leq M)

u_i \neq v_i (1 \leq i \leq M)

If i \neq j, (u_i, v_i) \neq (u_j, v_j).

1 \leq S, T \leq N

S \neq T

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
:
u_M v_M
S T

Output

If Ken cannot reach Vertex T from Vertex S by repeating ken-ken-pa, print -1.
If he can, print the minimum number of ken-ken-pa needed to reach vertex T.

Sample Input 1

4 4
1 2
2 3
3 4
4 1
1 3

Sample Output 1

2

Ken can reach Vertex 3 from Vertex 1 in two ken-ken-pa, as follows: 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 in the first ken-ken-pa, then 4 \rightarrow 1 \rightarrow 2 \rightarrow 3 in the second ken-ken-pa. This is the minimum number of ken-ken-pa needed.

Sample Input 2

3 3
1 2
2 3
3 1
1 2

Sample Output 2

-1

Any number of ken-ken-pa will bring Ken back to Vertex 1, so he cannot reach Vertex 2, though he can pass through it in the middle of a ken-ken-pa.

Sample Input 3

2 0
1 2

Sample Output 3

-1

Vertex S and Vertex T may be disconnected.

Sample Input 4

6 8
1 2
2 3
3 4
4 5
5 1
1 4
1 5
4 6
1 6

Sample Output 4

2



Sample input:
4 4
1 2
2 3
3 4
4 1
1 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
N, M = map(int, input().split())
if M == 0:
    print(-1)
    sys.exit()

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n

    def get_root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.get_root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self.get_root(x) == self.get_root(y)

    def union(self, x, y):
        r1 = self.get_root(x)
        r2 = self.get_root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2

#O(ElogV)
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

# ダイクストラ
import heapq

class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))


edge = [[] for i in range(N)]
ins = UnionFind(N)
route_map = [dict() for _ in range(N)]


for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    route_map[u][v] = 1
    edge[u].append([1,v])
    edge[v].append([1,u])
    ins.union(u, v)

S, T = map(int, input().split())
if ins.find(S-1, T-1) == False:
    print(-1)
    sys.exit()

# ゴールまでの最短経路
dijkstra_result = Dijkstra(route_map, S - 1,T-1).execute()

if dijkstra_heap(S-1)[T-1]%3 == 0:
    print(dijkstra_heap(S-1)[T-1]//3)
else:
    cur = 0
    for x in dijkstra_result:
        cur += 1
        a = 0
        for y in route_map[x].keys():
            if x in list(route_map[y].keys()):
                a = 1
                break
        if a != 0:
            break
        if cur == len(dijkstra_result):
            print(-1)
            sys.exit()
    print(dijkstra_heap(S-1)[T-1]//3+1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    # power_funcを用いて(nCk) mod p を求める 
    # nCk = n!/((n-k)!k!)を使用

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    # a^b mod p を求める
    # bを2進数分解して高速累乗

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

#D
def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge, g):

    dist = defaultdict(lambda: inf)
    dist[(start,0)] = 0
    q = [(dist[(start,0)], start, 0)]
    while q:
        du, u, t = heappop(q)
        for j in edge[u]:
            if t > 3:
                t = 0
            if dist[(j, t + 1)] > du + 1:
                dist[(j, t + 1)] = du + 1
                heappush(q, [dist[(j, t + 1)], j, t + 1])
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = defaultdict(list)
    for x,y in v:
        edge[x].append(y)
    d = dijkstra(n, s, edge, t)
    if d[(t,2)] == inf:
        print(-1)
    else:
        print(d[(t,2)])
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    b = list(set(s))
    a = len(list(set(s)))
    if a == 2 and s.count(b[0]) == s.count(b[1]) == 2:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = II()
    p = LI()
    ans = 0
    for i in range(1,n-1):
        if (p[i - 1] < p[i] and p[i] < p[i + 1]) or (p[i + 1] < p[i] and p[i] < p[i - 1]):
            ans += 1
    print(ans)
    return

#C
def C():
    n = II()
    d = LI()
    d.sort()
    ans = 0
    for i in range(10**5+1):
        if n // 2 == bisect_left(d, i):
            ans += 1
    print(ans)
    return


def combination_mod(n, k, mod):
    # power_funcを用いて(nCk) mod p を求める 
    # nCk = n!/((n-k)!k!)を使用

    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % mod
    b = factorial(k) % mod
    c = factorial(n - k) % mod
    return (a * power_func(b, mod - 2, mod) * power_func(c, mod - 2, mod)) % mod
    
def power_func(a, b, mod):
    # a^b mod p を求める
    # bを2進数分解して高速累乗

    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, mod)
        return d * d % mod
    if b % 2 == 1:
        return (a * power_func(a, b - 1, mod)) % mod

#D
def D():
    n, k = LI()
    ans = 0
    for i in range(1,k+1):
        a = combination_mod(n - k + 1, i, mod)
        b = combination_mod(k - 1, i - 1, mod)
        print((a*b)%mod)
    return

def dijkstra(num, start, edge, g):

    dist = defaultdict(int)
    dist[(start,0)] = 0
    q = [(dist[start], start, 0)]
    while q:
        du, u, t = heappop(q)
        for j in edge[u]:
            if t > 3:
                t = 0
            if dist[(j,t+1)] > du + 1:
                dist[(j, t + 1)] = du + 1
                heappush(q, [dist[(j,t+1)], j, t])
    return dist
#E
def E():
    n, m = LI()
    v = LIR_(m)
    s, t = LI_()
    edge = defaultdict(list)
    for x,y in v:
        edge[x].append(y)
    d = dijkstra(n, s, edge, t)
    if d[(t,2)] == inf:
        print(-1)
    else:
        print(d[(t,2)])
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))
d1 = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  d1[u].add(v)
s, t = list(map(int, input().split()))
d2 = defaultdict(set)

def dfs (x, nx, cnt, visited):
  if nx in visited:
    return
  if cnt==3:
    d2[x].add(nx)
  elif cnt>3:
    return

  for nnx in d1[nx]:
    dfs(x, nnx, cnt+1, visited)
  visited.add(nx)

for i in range(1, n+1):
  visited = set()
  dfs(i, i, 0, visited)
  visited.add(i)

def bfs():
  que = [(s, 0)]
  ans = 0
  visited = set()

  while len(que) > 0:
    p = que.pop(0)
    if p[0]==t:
      return p[1]+1
    for nx in d2[p[0]]:
      if nx in visited:
        continue
      visited.add(nx)
      que.append((nx, ans+1))
  return -1

print(bfs())

Submission status: Wrong Answer

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

UV = []
for _ in range(M):
    u, v = map(int, input().split())
    UV.append((u, v))
    
S, T = map(int, input().split())

from collections import defaultdict
G = defaultdict(lambda: [])

for u, v in UV:
    G[u].append(v)


def dfs(now, kenkenpa, count):
    if kenkenpa == 2 and now == T:
        return count
    
    if kenkenpa == 2 and count == 3:
        return 100
    
    if kenkenpa == 2:
        count += 1
    
    ret = 100
    kenkenpa = (kenkenpa + 1) % 3
    for next_v in G[now]:
        ret = min(ret, dfs(next_v, kenkenpa, count))
        
    return ret

ans = dfs(S, 2, 0)

if ans == 100:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())

visited = [False] * (n + 1)
link = []
for i in range(n + 1):
    link.append([])

dat = []
for i in range(m):
    u, v = map(int, input().split())
    dat.append((u, v))
    link[u].append((v))


s,t = map(int, input().split())
visited[s] = True # スタートはもう来てる

def hop(s, n):
    if n == 0:
        if visited[s] is not True:
            visited[s] = True
            return set([s])
        else:
            return set()

    res = set()
    for i in range(len(link[s])):
        res.update(hop(link[s][i], n - 1))
    return res

import collections
cur = collections.deque([])

cur.append((s,0))
hops = collections.deque([])
while len(cur) != 0:
    x = cur.pop()
    next, hopcount = x[0], x[1]
    r = hop(next, 3)
    r = list(r)
    for i in range(len(r)):
        if r[i] == t:
            hops.append(hopcount + 1)
        cur.append( (r[i], hopcount + 1) )


if len(hops) == 0:
    print(-1)
else:
    print(min(hops))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 29 20:53:20 2019

@author: Yamazaki Kenichi
"""
from collections import deque
import sys

N, M = map(int,input().split())
uv = [list(map(int,input().split())) for i in range(M)]
S, T = map(int,input().split())

Ta = [[] for i in range(N+1)]
for c in uv:
    Ta[c[0]].append(c[1])

counta = 0
rout = [[] for i in range(N+1)]
while len(rout[S]) < 3:
    next_ = deque([S])
    for i in range(3):
        for j in range(len(next_)):
            tmp = next_.popleft()
            for k in Ta[tmp]:
                next_.append(k)
            rout[tmp].append(i)
        
        if rout[T].count(2) >= 1:
            print(counta)
            sys.exit()
        counta += 1
print(-1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
f = [[] for i in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    f[u].append(v)

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

used = [-1 for i in range(n)]

Now = [s]
time = 0
Next = []
while len(Now) > 0:
    now = Now.pop()
    if used[now] != -1:
        continue
    else:
        used[now] = time
    #print(now)
    if now == t:
        print(time)
        exit()
    First = f[now]
    #print(First)
    for second in First:
        Second = f[second]
        #print(Second)
        for next in Second:
            Next += f[next]

    if len(Now) == 0:
        Now = Next
        time += 1
        Next = []

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

ans = 0
queue = [S]
visit = set()
while len(queue) > 0:
    queuetemp = set()
    for now in queue:
        if now in visit:
            continue
        visit.add(now)
        queuenext = set(graph[now])
        for _ in range(2):
            nextqueue = set()
            for next in queuenext:
                nextqueue = nextqueue | set(graph[next])
        queuetemp = queuetemp | nextqueue
    queue = queuetemp
    if T in visit:
        break
    ans += 1



if T in visit:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  if t>5*(10**6):
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      for vv in graph[v]:
        if not table[vv][t%3]:
          nlist.append(vv)
          table[vv][t%3]=True
      
  #print((t,nlist))
  vlist = nlist

Submission status: Wrong Answer

Solution code:
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())

Submission status: Wrong Answer

Solution code:
from queue import Queue

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

visited = [-1 for j in range(n+1)]
visit = Queue()


for v1,v2 in v:
    if v1 == s:
        visit.put((v2, 0))
    if v2 == s:
        visit.put((v1, 0))

while visit:
    now, step = visit.get()
    visited[now] = 1

    if now == t:
        print(step+1)
        exit()

    elif step <= 3:

        for v1,v2 in v:
            if v1 == now and visited[v2] != 1:
                visit.put((v2, step + 1))
            if v2 == now and visited[v1] != 1:
                visit.put((v1, step + 1))

print(-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split(" "))
v = {}
for i in range(M):
    v1, v2 = map(int,input().split(" "))
    v[i+1] = int(v2)
S, T = map(int,input().split(" "))

print(v)

length = len(v)

if length%3 == 0:
    length = int(length / 3)
    for i in range(1,length+1):
        if T == v[i*3]:
            print(i)
            break
    print("-1")
else:
    for i in range(len(v)):
        for j in range(3):
            S = v[S]
        print(S) 
        if T == S:
            print(i)
            break
    print('-1')

Submission status: Wrong Answer

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

G = [[] for _ in range(M)]

for i in range(M):
    u, v = map(int, input().split())
    G[u-1].append(v-1)

S, T = map(int, input().split())
S -= 1
T -= 1


stack = [S]
kaisuu = [0]
otozureta = [False for _ in range(M)]
otozureta1 = [False for _ in range(M)]
otozureta2 = [False for _ in range(M)]


phase = [0]


ans = -3
try:
    while len(stack) > 0:
        pos = stack.pop()
        step = kaisuu.pop()
        ph = phase.pop()

        if ph == 0:
            otozureta[pos] = True
            if pos == T:
                ans = step
                break
        elif ph == 1:
            otozureta1[pos] = True
        else:
            otozureta2[pos] = True

        for n in G[pos]:
            if ph == 2 and otozureta[n]:
                pass
            elif ph == 0 and otozureta1[n]:
                pass
            elif ph == 1 and otozureta2[n]:
                pass
            else:
                stack.append(n)
                kaisuu.append(step+1)
                phase.append((ph + 1) % 3)

    print(ans//3)
except:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
uv = LIR(M)
S, T = LI()
S, T = S-1, T-1

edge = [[0]*N for i in range(N)]
utov = [[] for i in range(N)]

for u, v in uv:
    edge[u-1][v-1] = 1
    utov[u-1].append(v-1)


kenken = []

def bfs(s):
    ret = []
    bfs_map = [-1]*N
    q = deque()
    q.append(s)
    bfs_map[s] = 0
    while q:
        u = q.popleft()
        for v in utov[u]:
            if (edge[u][v] > 0) and (bfs_map[u] > bfs_map[v]):
                bfs_map[v] = bfs_map[u] + 1
                if (bfs_map[v] == 3):
                    ret.append(v)
                else:
                    q.append(v)
    return ret

for i in range(N):
    ret = bfs(i)
    kenken.append(ret)

kenkenedge = [[0]*N for i in range(N)]
for u, vs in enumerate(kenken):
    for v in vs:
        kenkenedge[u][v] = 1

def bfs_dist(S, T):
    bfs_map = [-1]*N
    q = deque()
    q.append(S)
    bfs_map[S] = 0
    while q:
        u = q.popleft()
        for v in kenken[u]:
            if (kenkenedge[u][v] > 0) and (bfs_map[u] > bfs_map[v]):
                bfs_map[v] = bfs_map[u] + 1
                if (v==T):
                    return bfs_map[T]
                else:
                    q.append(v)
    return -1

print(bfs_dist(S, T))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())

visited = [False] * (n + 1)
link = []
for i in range(n + 1):
    link.append([])

dat = []
for i in range(m):
    u, v = map(int, input().split())
    dat.append((u, v))
    link[u].append((v))


s,t = map(int, input().split())
visited[s] = True # スタートはもう来てる

def hop(s, n):
    if n == 0:
        if visited[s] is not True:
            visited[s] = True
            return set([s])
        else:
            return set()

    res = set()
    for i in range(len(link[s])):
        res.update(hop(link[s][i], n - 1))
    return res

import collections
cur = collections.deque([])

cur.append((s,0))
hops = []
while len(cur) != 0:
    x = cur.pop()
    next, hopcount = x[0], x[1]
    r = hop(next, 3)
    r = list(r)
    for i in range(len(r)):
        if r[i] == t:
            hops.append(hopcount + 1)
        cur.append( (r[i], hopcount + 1) )


if len(hops) == 0:
    print(-1)
else:
    print(min(hops))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
tmpmat = {i:set() for i in range(1,n+1)}

mat = {i:set() for i in range(1,n+1)}

u,v = None,None
for _ in range(m):
  u,v = map(int,input().split())
  tmpmat[u].add(v)
  
s,t = map(int,input().split())

for i in range(1,n+1):
  node2s = set()
  for node1 in tmpmat[i]:
    node2s |=(tmpmat[node1])
  for node2 in node2s:
    mat[i] |= tmpmat[node2]

visited = [False for i in range(n+1)]

ans= 100000000000000000

que = [(s,0)]

while que:
  node,count = que.pop()
  visited[node] = True
  
  for newnode in mat[node]:
    if newnode == t:
      ans = min(ans,count+1)
    elif not visited[newnode]:
      que.append((newnode,count+1))

if ans == 100000000000000000:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
def kenpa(s, d, N):
    for i in range(N):
        if s not in d.keys():
          return -1
        s = d[s]
    return s


N, M = list(map(int, input().split()))
d = dict()
for i in range(M):
    u, v = list(map(int, input().split()))
    d[u] = v
s, e = list(map(int, input().split()))
count = 0
while True:
    j = kenpa(s, d, N)
    if j == s or j==-1:
        print(-1)
        break
    elif e == j:
        print(count)
        break
    else:
        s = j

Submission status: Wrong Answer

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

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  if t>10**7:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      for vv in graph[v]:
        if not table[vv][t%3]:
          nlist.append(vv)
          table[vv][t%3]=True
      
  #print((t,nlist))
  vlist = nlist

Submission status: Wrong Answer

Solution code:
import queue
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, V):
    color = [WHITE for i in range(N+1)]
    d = [INFTY for i in range(N+1)]
    d[s] = 0
    q = queue.Queue()
    q.put(s)

    while not q.empty():
        u = q.get()
        color[u] = BLACK

        for v in V[u]:
            if color[v] != BLACK:
                d[v] = d[u] + 1
                color[v] = GRAY
                q.put(v)

    return d

def rec(s, i, depth):
    if depth == 3:
        kkpgraph[s].append(i)
        return
    if not graph[i]:
        return
    for node in graph[i]:
        rec(s, node, depth+1)
    return

N, M = map(int, input().split())
graph = [[] for i in range(N+1)]
kkpgraph = [[] for i in range(N+1)]
for i in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
S, T = map(int, input().split())
for i in range(1, N+1):
    rec(i, i, 0)
d = dijkstra(S, kkpgraph)
if d[T] == INFTY:
    print(-1)
else:
    print(d[T])

Submission status: Wrong Answer

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

graph=[]
for _ in range(N+1):
  graph.append([])

uvlist = []
for i in range(M):
  u,v=map(int,input().split())
  graph[u].append(v)
  
S,T=map(int,input().split())

#print(graph)
table=[]
for i in range(N+1):
  table.append([False]*3)
#print(table)  
  
vlist=graph[S]
table[S][0]=True
t=0
while(True):
  t+=1
  if t>10**6:
    print(-1)
    sys.exit()
  
  nlist = []
  for v in vlist:
    if v == T and t%3 == 0:
      print(t//3)
      sys.exit()
    else:
      for vv in graph[v]:
        if not table[vv][t%3]:
          nlist.append(vv)
          table[vv][t%3]=True
      
  #print((t,nlist))
  vlist = nlist

Submission status: Wrong Answer

Solution code:
N,M = map(int, raw_input().split(' '))
uv = []
for m in range(M):
     uv.append(map(int, raw_input().split(' ')))

S,T = map(int, raw_input().split(' '))


def kenken(root, edges):
      n_next = []
      for e in edges:
            if e[0] == root:
                  n_next.append(e[1])
      n_nextnext = []
      for n_n in n_next:
            for ee in edges:
                  if ee[0] == n_n:
                        n_nextnext.append(ee[1])
      n_nextnext = list(set(n_nextnext))
      n_nextnextnext = []
      for n_nn in n_nextnext:
            for eee in edges:
                  if eee[0] == n_nn:
                        n_nextnextnext.append(eee[1])
      n_nextnextnext = list(set(n_nextnextnext))

      return(n_nextnextnext)

blacklist = [S]
count = 0

aaa = [S]
AAA = []
while True:
     AAA = []
     count += 1
     for tt in aaa:
          aaa = kenken(tt, uv)
          if T in aaa:
               print(count)
               break
          for b in blacklist:
               if b in aaa:
                    aaa.remove(b)
          AAA.append(aaa)
     if AAA == []:
          print(-1)
          break
     blacklist.append(aaa)

Submission status: Wrong Answer

Solution code:
import sys
import itertools

N, M = map(int, input().split())
nexts = dict()
for i in range(N):
    nexts.setdefault(i + 1, [])
for _ in range(M):
    u, v = map(int, input().split())
    nexts[u].append(v)
S, T = map(int, input().split())

dist = 0
dists = [-1] * 3
queue = [S]
while len(queue) > 0:
    next_queue = []
    for n in queue:
        if n == T:
            m = dist % 3
            if m == 0:
                print(dist // 3)
                sys.exit()
            elif dists[m] == -1:
                dists[m] = dist
        else:
            next_queue.extend(nexts[n])
    if dists[1] > 0 and dists[2] > 0:
        break
    queue = next_queue
    dist += 1

dist = 0
dists_rev = [-1] * 3
queue = [T]
while len(queue) > 0:
    next_queue = []
    for n in queue:
        if n == S:
            m = dist % 3
            if dists_rev[m] == -1:
                dists_rev[m] = dist
        else:
            next_queue.extend(nexts[n])
    if dists_rev[0] > 0 and dists_rev[1] > 0 and dists_rev[2] > 0:
        break
    queue = next_queue
    dist += 1

ans = -1
if dists[1] > 0 and dists_rev[1] > 0:
    a = (dists[1] * 2 + dists_rev[1]) // 3
    ans = max(ans, a)
if dists[2] > 0 and dists_rev[2] > 0:
    a = (dists[2] * 2 + dists_rev[2]) // 3
    ans = max(ans, a)
if dists[1] > 0 and dists_rev[0] > 0:
    a = (dists[1] * 3 + dists_rev[0] * 2) // 3
    ans = max(ans, a)
if dists[2] > 0 and dists_rev[0] > 0:
    a = (dists[1] * 3 + dists_rev[2] * 2) // 3
    ans = max(ans, a)
print(ans)

Submission status: Wrong Answer

Solution code:
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())