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
def input(): return sys.stdin.readline().strip()
def main():
    N, M = map(int, input().split())
    List = [[] for _ in range(N)]
    
    for i in range(M):
        u, v = map(int, input().split())
        List[u-1].append(v-1)
        
    S, T = map(int, input().split())

    ans = -1
    flag = [True]*N
    que = [(S-1, 0)]
    while que:
        edge = que.pop()
        if edge[0]==T-1:
            ans = edge[1]
            break
        step=edge[1]
        for j in List[edge[0]]:
            for k in List[j]:
                for l in List[k]:
                    if flag[l]:
                        que.append((l, step+1))
                        flag[l]=False
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
g -= 1
co = Max
def dfs(x,nn,now,coun):
    global sss,g,co
    if min(sss[now][nn],coun) == coun:
        if now == g and nn == 0:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            for i in x[now]:
                if nn == 2:
                    nn = 0
                    coun += 1
                else:
                    nn += 1
                dfs(x,nn,i,coun)
    else:
        if now == g and nn == 0:
            co = min(co,coun)
dfs(s,0,st-1,0)
if co == Max:
    print(-1)
else:
    print(co)

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 | queuenext
    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>300003:
    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 sys

sys.setrecursionlimit(1000000)

words = lambda t : list(map(t, input().split()))


def dfs(ns,s,t):
    n_steps = [[-1] * len(ns) for i in range(3)]
    def search(i, step):
        #print(i, step, n_steps)
        if step % 3 == 0 and i == t:
            return
        j = step % 3
        if n_steps[j][i] == -1 or (n_steps[j][i] > step):
            n_steps[j][i] = step
            for next in ns[i]:
                cand = search(next, step+1)

    search(s, 0)
    if n_steps[0][t] == -1:
        print(-1)
    else:
        print(n_steps[0][t] // 3)

def main():
    n,v = words(int)
    ns = [[] for _ in range(n)]
    for _ in range(v):
        (st,end) = map(int,input().split())
        ns[st-1].append(end - 1)
    s,t = words(int)
    dfs(ns,s-1,t-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

def kkp_iter(s, neighbor, d, cnt):
    if cnt == 3:
        d.add(s)
        return

    for n in neighbor[s]:
        kkp_iter(n, neighbor, d, cnt+1)


def kkp(s, neighbor):
    d = set ()
    kkp_iter(s, neighbor, d, 0)
    return d


n, m = map(int, input().split())

neighbor = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    neighbor[u].append(v)

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

gone = set()
q = []

dest_t = False
kkp_cnt = 0
while not dest_t:
    gone.add(s)
    next_s = kkp(s, neighbor)
    kkp_cnt += 1

    for ns in next_s:
        if ns == t:
            dest_t = True
            break
        elif ns in gone:
            continue
        else:
            q.append(ns)

    if len(q) > 0:
        s = q.pop(0)
    else:
        break

if dest_t:
    print(kkp_cnt)
else:
    print(-1)

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

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

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

        for n in G[pos]:
            if ph == 2 and otozureta[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:
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


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


for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, 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()

if dijkstra_heap(S-1)[T-1]%3 == 0:
    print(dijkstra_heap(S-1)[T-1]//3)
else:
    print(dijkstra_heap(S-1)[T-1]//3+1)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    List = [[] for _ in range(N)]
    
    for i in range(M):
        u, v = map(int, input().split())
        List[u-1].append(v-1)
        
    S, T = map(int, input().split())

    ans = -1
    flag = [True]*N
    que = [(S-1, 0)]
    while que:
        edge = que.pop()
        if edge[0]==T-1:
            ans = edge[1]
            break
        step=edge[1]
        for j in List[edge[0]]:
            for k in List[j]:
                for l in List[k]:
                    if flag[l]:
                        que.append((l, step+1))
                        flag[l]=False
    print(ans)
if __name__ == '__main__':
    main()

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)

vlist=graph[S]
t=0
while(True):
  t+=1
  if t>10**5:
    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]:
        nlist.append(vv)
      
  #print((t,nlist))
  vlist = nlist

Submission status: Wrong Answer

Solution code:
import sys
import collections


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    graph = collections.defaultdict(set)
    for _ in range(m):
        u, v = [int(s) for s in sys.stdin.readline().strip().split()]
        graph[u].add(v)
    s, t = [int(s) for s in sys.stdin.readline().strip().split()]

    shortest = dict()
    shortest[s] = 0
    q = collections.deque()
    q.append(s)
    turn = 1
    while q:
        cur = q.pop()
        cur_nodes = {cur}
        next_nodes = set()
        for _ in range(3):
            for cur_node in cur_nodes:
                next_nodes = next_nodes.union(graph[cur_node])
            cur_nodes = next_nodes
            next_nodes = set()
        for cur_node in cur_nodes:
            if cur_node not in shortest:
                if cur_node == t:
                    print(turn)
                    return
                shortest[cur_node] = turn
                q.append(cur_node)
        turn += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())
E = {u: set() for u in range(1, N+1)}
for i in range(M):
    u, v = map(int, input().split())
    E[u].add(v)
S, T = map(int, input().split())

X = {}
for u in E:
    for i in range(3):
        X[(u, i)] = set([(v, (i + 1) % 3) for v in E[u]])

# bfs
queue = deque(maxlen=N)
queue.append(((S, 0), 0))
visited = set()

while len(queue) > 0:
    u, n = queue.popleft()
    if u in visited:
        continue
    visited.add(u)
    if u == (T, 0):
        print(n // 3)
        exit()
    for v in X[u]:
        queue.append((v, n + 1))

print(-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
E = [[] for i in range(N)]
RE = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  E[u - 1].append(v - 1)
  RE[v - 1].append(u - 1)
S, T = map(int, input().split())
RD = [-1] * N
RD[T - 1] = 0
Q = [T - 1]
while Q:
  q = Q.pop(0)
  for adj in RE[q]:
    if RD[adj] == -1:
      RD[adj] = RD[q] + 1
      Q.append(adj)
if RD[S - 1] == -1:
  print(-1)
else:
  D = [[-1, -1, -1] for i in range(N)]
  Q = [[S - 1, 0]]
  while Q:
    q, d = Q.pop(0)
    m = (d + RD[q]) % 3
    if D[q][m] != -1:
      continue
    D[q][m] = d + RD[q]
    if m != 0:
      for adj in E[q]:
        Q.append([adj, d + 1])
  P = [d[0] for d in D if d[0] != -1]
  if P:
    print(min(P) // 3)
  else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()
S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [mod for i in range(N)]

# print(routes)
def skip(now,move_cnt):
    flag = True
    if move_cnt % 3 == used[now] % 3 and move_cnt > used[now]:
        flag = False
    if move_cnt % 3 == 0:
        if used[now] > move_cnt//3:
            used[now] = move_cnt//3
        else:
            flag = False
    if flag:
        for route in routes[now]:
            skip(route,move_cnt+1)

skip(S,0)
try:
    ans = used[T]
    if ans == mod:
        ans = -1
except:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

ELIST=[set() for i in range(N+1)]

for x,y in E:
    ELIST[x].add(y)

ELIST2=[set() for i in range(N+1)]

for i in range(N+1):
    for j in ELIST[i]:
        ELIST2[i]=ELIST2[i]|ELIST[j]

ELIST3=[set() for i in range(N+1)]

for i in range(N+1):
    for j in ELIST2[i]:
        ELIST3[i]=ELIST3[i]|ELIST[j]

DIS=[-1]*(N+1)
from collections import deque
DIS[S]=0
S=deque([S])

i=1

while S:
    x=S.pop()
    NEWS=deque()

    for to in ELIST3[x]:
        if DIS[to]==-1:
            DIS[to]=i
            NEWS.append(to)

    i+=1
    S=NEWS

print(DIS[G])

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


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


for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, 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()

if dijkstra_heap(S-1)[T-1]%3 == 0:
    print(dijkstra_heap(S-1)[T-1]//3)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import time
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

t = time.time()
N, M = MAP()

uv = [LIST() for _ in range(M)]
S, T = MAP()
S = S-1
T = T-1
graph = defaultdict(list)
flag = False
for u, v in uv:
	if v-1 == T:  # T にたどりつける
		flag = True
	graph[u-1].append(v-1)
if not flag:
	print(-1)
	sys.exit(0)
# print(graph)
q = deque([])
q.append((S, 0))

while q:
	if time.time() - t >= 1.5:  # 時間内に見つけられなかった.
		print(-1)
		break
	search, step = q.popleft()
	# print(search, step)
	if search == T and step%3 == 0:
		print((step+1)//3)
		break

	for node in graph[search]:
		q.append((node, step+1))

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    List = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        List[u-1].append(v-1)
    S, T = map(int, input().split())
    que = [(S-1, 0)]
    node = [[] for _ in range(N)]
    for i in range(N):
        for j in List[i]:
            for k in List[j]:
                for l in List[k]:
                    node[i].append(l)
    step = 0
    ans = -1
    flag = [True]*N
    while que:
        edge = que.pop()
        if edge[0]==T-1:
            ans = edge[1]
            break
        step=edge[1]
        for i in node[edge[0]]:
            if flag[i]:
                que.append((i, step+1))
                flag[i]=False
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

path_list = [[] for _ in range(n)]

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

s, t = map(int, input().split())
s -= 1
t -= 1
i = 0
dp = [[] for _ in range(3*n)]
dp[0].append(s)
while i < 2*n-1:
  a = set()
  for dot in dp[i]:
    a |= set(path_list[dot])
  if not -~i%3 and t in a:
    print(-~i//3)
    exit()
  dp[i+1] = a
  i += 1
print(-1)

Submission status: Wrong Answer

Solution code:
def dfs_tri(f,N,t, u):
    f_1 = [False for i in range(N)]
    f_2 = [False for i in range(N)]
    for u_1 in t[u]:
        for u_2 in t[u_1]:
            if not (f_1[u_2]) and (f[u_2]):
                f_1[u_2] =True
                for u_3 in t[u_2]:
                    f_2[u_3] = True

    return f_2


N,M = [int(x) for x in input().split()]
f = [True for i in range(N)]
t = [[]for i in range(N)]
for i in range(M):
    u,  v= [int(x) for x in input().split()]
    t[u-1].append(v-1)
S,T = [int(x) for x in input().split()]
i = 0
r =[S-1]
while(True):
    i += 1
    if len(r) == 0:
        print(-1)
        exit()
    r_ =[]
    for u in r:
        ret = (dfs_tri(f,N,t,u))
       # print(ret,u)
        for v in range(N):
            if ret[v] and v == T-1:
                print(i)
                exit()
            if ret[v] and f[v]:
                r_.append(v)
                f[v] = False
    r =r_

Submission status: Wrong Answer

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

path_list = [[] for _ in range(n)]

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

s, t = map(int, input().split())
s -= 1
t -= 1
i = 0
dp = [[] for _ in range(3*n)]
dp[0].append(s)
while i < n-1:
  a = set()
  for dot in dp[i]:
    a |= set(path_list[dot])
  if not -~i%3 and t in a:
    print(-~i//3)
    exit()
  dp[i+1] = a
  i += 1
print(-1)

Submission status: Wrong Answer

Solution code:
# 頂点を3回ずつに持つ (x歩目の着地）
# 最短路

import sys
import numpy as np
from scipy.sparse import *
input = sys.stdin.readline
N,M = map(int,input().split())
if M == 0:
  print(-1)
  exit()
UV = np.array([input().split() for _ in range(M)], dtype=np.int32)
U = UV[:,0] * 3
V = UV[:,1] * 3
S,T = map(int,input().split())

rows = np.zeros(3*M, dtype=np.int32)
cols = np.zeros(3*M, dtype=np.int32)

rows[:M] = U
rows[M:2*M] = U + 1
rows[2*M:] = U + 2
cols[:M] = V + 1
cols[M:2*M] = V + 2
cols[2*M:] = V

graph = csr_matrix((np.ones_like(rows), (rows, cols)), (3*N+3, 3*N+3))
#dist = csgraph.dijkstra(graph, indices = 3*S)

#answer = -1 if dist[3*T] > 3*N else int(dist[3*T]//3)
#print(answer)

Submission status: Wrong Answer

Solution code:
import copy

N,M = map(int,input().split())
G = [set() for i in range(N)]
for _ in range(M):
    s,t = map(int,input().split())
    G[s-1].add(t)
S,T = map(int,input().split())

pque = set()
que = set([1])
nque = set()
ans = 0

while T not in que and len(que) != 0:
    que = que - pque
    pque = que | pque
    for _ in range(3):
    
        for s in que:
            for t in G[s-1]:
                nque.add(t) 

        que = copy.copy(nque)
        nque.clear()
    ans += 1

if len(que) == 0: ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
uv=[]
for _ in range(M):
    uv.append([int(i) for i in input().split()])
S,T=map(int,input().split())

uv.sort()

childlist=[]
for _ in range(N):
    childlist.append([])

for i in range(M):
    p=uv[i][0]-1
    childlist[p].append(uv[i][1]-1)

q=[S-1]
MAP=[-1]*N
MAP[S-1]=0

step=0
while q:
    x = q.pop(0)
    for next in childlist[x]:
        MAP[next]=MAP[x]+1
        if next==T-1 and MAP[next]%3==0:
            print((step+1)//3)
            break
        q.append(next)
    step+=1
    if step//3 > 5*N:
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
import sys
import collections


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    graph = collections.defaultdict(set)
    for _ in range(m):
        u, v = [int(s) for s in sys.stdin.readline().strip().split()]
        graph[u].add(v)
    s, t = [int(s) for s in sys.stdin.readline().strip().split()]

    shortest = dict()
    q = collections.deque()
    q.append(s)
    turn = 1
    while q:
        cur = q.pop()
        cur_nodes = [cur]
        next_nodes = []
        for _ in range(3):
            for cur_node in cur_nodes:
                next_nodes += list(graph[cur_node])
            cur_nodes = next_nodes
            next_nodes = []
        for cur_node in cur_nodes:
            if cur_node not in shortest:
                if cur_node == t:
                    print(turn)
                    return
                shortest[cur_node] = turn
                q.append(cur_node)
        turn += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import collections

def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    graph = collections.defaultdict(set)
    for _ in range(m):
        u, v = [int(s) for s in sys.stdin.readline().strip().split()]
        graph[u].add(v)
    s, t = [int(s) for s in sys.stdin.readline().strip().split()]

    shortest = dict()
    q = collections.deque()
    q.append(s)
    turn = 1
    while q:
        cur = q.pop()
        cur_nodes = [cur]
        next_nodes = []
        for _ in range(3):
            for cur_node in cur_nodes:
                next_nodes += list(graph[cur_node])
            cur_nodes = next_nodes
            next_nodes = []
        for cur_node in cur_nodes:
            if cur_node not in shortest:
                if cur_node == t:
                    print(turn)
                    return
                shortest[cur_node] = turn
                q.append(cur_node)
        turn += 1
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

inf = 10 ** 6

def main():
    n, m = [int(i) for i in sys.stdin.readline().strip().split()]
    edges = [tuple(int(i) for i in sys.stdin.readline().strip().split()) for j in range(m)]
    e_dict = {i: [] for i in range(1, n+1)}
    s, t = [int(i) for i in sys.stdin.readline().strip().split()]

    for a, b in edges:
        e_dict[a].append(b)

    ret = -1
    loop = 0
    log = [-1] + [10 ** 8] * n
    que = []
    que.append((s, 0))
    log[s] = 0
    while len(que):
        loop += 1
        if loop > inf:
            break
        nod, st = que.pop(0)
        if nod == t and st % 3 == 0:
            ret = st // 3
            break
        for u in e_dict[nod]:
            if log[s] == 10**8 or log[s] % 3 != (st+1) // 3:
                que.append((u, st+1))
    return ret
    
print(main())

Submission status: Wrong Answer

Solution code:
import sys
import time
time0=time.time()
input = sys.stdin.readline

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

ELIST=[set() for i in range(N+1)]

for x,y in E:
    ELIST[x].add(y)

check=[10**8]*(N+1)
check[S]=0

def three_step_from(S,i):

    ONE=set()

    for s in S:

        ONE=ONE|ELIST[s]

    TWO=set()
    for one in ONE:
        
        TWO=TWO|ELIST[one]

    THREE=set()
    for two in TWO:
        THREE=THREE|ELIST[two]

    RET=set()

    for three in THREE:
        if check[three]!=10**8:
            continue
        check[three]=i
        RET.add(three)

    return RET

i=1
NOW={S}
while NOW:
    NOW=three_step_from(NOW,i)
    i+=1

    if check[G]!=10**8:
        print(check[G])
        sys.exit()

    if time.time()-time0>1.8:
        print(-1)
        sys.exit()

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M = i2nn()
    UV = ii2nnn(M)
    S, T = i2nn()
    to = [[] for _ in range(N+1)]
    for u, v in UV:
        to[u].append(v)
    bit = [0] * (N+1)
    q = deque()
    q.append((S, 1, 0))
    while q:
        i, b, c = q.pop()
        if b & bit[i] == b:
            continue
        if i == T and (b & 1) == 1:
            print(c//3)
            return
        bit[i] |= b
        b2 = bit[i] << 1
        if b2 >= 8:
            b2 -= 7
        for j in to[i]:
            q.append((j, b2, c+1))
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from math import ceil

N, M = map(int, input().split())
graph = {i: [[], -1] for i in range(1, N + 1)}
for _ in range(M):
    u, v = map(int, input().split())
    graph[u][0].append(v)
    graph[v][0].append(u)
S, T = map(int, input().split())


def bfs():
    que = deque()
    que.append(S)
    graph[S][1] = 0
    while len(que) != 0:
        p = que.popleft()
        if p == T:
            return graph[p][1]
        for i in graph[p][0]:
            if graph[i][1] != -1:
                continue
            graph[i][1] = graph[p][1] + 1
            que.append(i)
    return -1


cnt = bfs()
if cnt == -1:
    print(cnt)
elif cnt % 3 == 0 or cnt % 3 == 1:
    print(ceil(cnt / 3))
elif cnt % 3 == 2:
    print(ceil(cnt / 3) + 1)

Submission status: Wrong Answer

Solution code:
import heapq

n, m = [int(i) for i in input().split()]
U = [[int(i) for i in input().split()] for j in range(m)]
s, t = [int(i) for i in input().split()]

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

for u, v in U:
    E[u].append(v)

visited = [0] * (n + 1)

V = []
heapq.heappush(V, (0, s))

while V:
    c, v = heapq.heappop(V)
    if v == t and c % 3 == 0:
        print(c // 3)
        exit()
    if visited[v] == 10:
        continue
    visited[v] += 1

    for to in E[v]:
        heapq.heappush(V, (c + 1, to))

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, M = map(int, input().split())
E = {u: set() for u in range(1, N+1)}
for i in range(M):
    u, v = map(int, input().split())
    E[u].add(v)
S, T = map(int, input().split())

X = {u: set([u]) for u in range(1, N+1)}
for i in range(3):
    for u in X:
        Y = set()
        for v in X[u]:
            Y.update(E[v])
        X[u] = Y

# bfs
queue = deque(maxlen=N)
queue.append((S, 0))
visited = set()

while len(queue) > 0:
    u, n = queue.popleft()
    if u in visited:
        continue
    visited.add(u)
    if u == T:
        print(n)
        exit()
    for v in X[u]:
        queue.append((v, n + 1))

print(-1)