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

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
for i in range(m):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    #undirected->erase#edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

    #undirected->erase#edges[__].append(_)
    """
"""#weighted->erase

s,T=map(int,input().split())
from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=set()
seen.add(3*s)
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if t not in seen:
            dq.append((t,c+1))
            seen.add(now)

print("-1")

Submission status: Time Limit Exceeded

Solution code:
def f():
    import sys
    input=sys.stdin.buffer.readline
    inputs=sys.stdin.buffer.readlines
    sys.setrecursionlimit(10**9)
    n,m=map(int,input().split())
    edges=[[] for i in range(3+3*n)]
    for i in range(m):
        """#weighted->erase_,__,___=map(int,input().split())
        edges[_].append((__,___))
        #undirected->erase#edges[__].append((_,___))
        """
        _,__=map(int,input().split())
        _*=3;__*=3
        edges[_].append(__+1)
        edges[_+1].append(__+2)
        edges[_+2].append(__)

        #undirected->erase#edges[__].append(_)
        """
    """#weighted->erase

    s,T=map(int,input().split())
    from collections import deque
    dq=deque([])
    dq.append((3*s,0))
    T*=3
    seen=set()
    seen.add(3*s)
    while dq:
        now,c=dq.popleft()
        if now==T :print(c//3);exit()
        for t in edges[now]:
            if t not in seen:
                dq.append((t,c+1))
                seen.add(now)

    print("-1")
if __name__ == "__main__":
    f()

Submission status: Time Limit Exceeded

Solution code:
def f():
    import sys
    input=sys.stdin.buffer.readline
    inputs=sys.stdin.buffer.readlines
    sys.setrecursionlimit(10**9)
    n,m=map(int,input().split())
    edges=[[] for i in range(3+3*n)]
    for i in range(m):
        """#weighted->erase_,__,___=map(int,input().split())
        edges[_].append((__,___))
        #undirected->erase#edges[__].append((_,___))
        """
        _,__=map(int,input().split())
        _*=3;__*=3
        edges[_].append(__+1)
        edges[_+1].append(__+2)
        edges[_+2].append(__)

        #undirected->erase#edges[__].append(_)
        """
    """#weighted->erase

    s,T=map(int,input().split())
    from collections import deque
    dq=deque([])
    dq.append((3*s,0))
    T*=3
    seen=set()
    while dq:
        now,c=dq.popleft()
        seen.add(now)
        for t in edges[now]:
            if t==T :print((c+1)//3);exit()
            if t not in seen:
                dq.append((t,c+1))
    print("-1")
if __name__ == "__main__":
    f()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
for i in range(m):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    #undirected->erase#edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

    #undirected->erase#edges[__].append(_)
    """
"""#weighted->erase

s,T=map(int,input().split())
from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=set()
while dq:
    now,c=dq.popleft()
    seen.add(now)
    for t in edges[now]:
        if t==T :print((c+1)//3);exit()
        if t not in seen:
            dq.append((t,c+1))
print("-1")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
edges=[[] for i in range(1+n)]
for i in range(m):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    #undirected->erase#edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    edges[_].append(__)
    #undirected->erase#edges[__].append(_)
    """
"""#weighted->erase

s,T=map(int,input().split())
from collections import deque
dq=deque([])
dq.append((s,0,0))
seen=[set()for i in [0,0,0]]
while dq:
    now,o,c=dq.popleft()
    seen[o].add(now)
    nex=(o+1)%3
    for t in edges[now]:
        if t==T and nex==0:print((c+1)//3);exit()
        if not(t in seen[nex]):
            dq.append((t,nex,c+1))
print("-1")

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
edges=[[] for i in range(1+n)]
for i in range(m):
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    #undirected->erase#edges[__].append((_,___))
    """
    _,__=map(int,input().split())
    edges[_].append(__)
    #undirected->erase#edges[__].append(_)
    """
"""#weighted->erase
s,t=map(int,input().split())
r1,r2,r0=set(),set(),set()
from collections import deque
d0=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
d1=deque([])
d2=deque([])
d0.append((s,0))
r0.add(s)
while d0 :
    while d0:
        a,c=d0.pop()
        for ne in edges[a]:
            if ne not in r1:d1.appendleft((ne,c))
    while d1:
        a,c=d1.pop()
        for ne in edges[a]:
            if ne not in r2:d2.appendleft((ne,c))
    while d2:
        a,c=d2.pop()
        for ne in edges[a]:
            if ne not in r0:
                if ne != t:d0.appendleft((ne,c+1))
                else:print(c+1);exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

def main():

  n,m=map(int,input().split())
  d=[[0 for i in range(n)] for i in range(n)]
  to=[[] for i in range(n)]
  for i in range(m):
    u,v=map(lambda x:int(x)-1,input().split())
    to[u].append(v)
  s,t=map(lambda x:int(x)-1,input().split())

  #print(to)

  # calc d (after 3 times dist)
  for i in range(n):
    first,second,third=[],[],[]
    for j in to[i]:
      first.append(j)
    for j in first:
      for k in to[j]:
        second.append(k)
    for j in second:
      for k in to[j]:
        third.append(k)
        d[i][k]=1

  ans=dijkstra(csr_matrix(d),indices=0).astype(int)
  print(ans[t] if ans[t]>0 else -1)


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
to = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    to[a].append(b)

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

q = [(S, 0)]
v = [[-1] * 3 for i in range(N+1)]

while q != []:
    a, t = q.pop(0)
    b = t % 3
    if v[a][b] != -1:
        continue
    v[a][b] = t
    t += 1
    for x in to[a]:
        q.append((x, t))
    #print(q)

if v[T][0] == -1:
    print("-1")
else:
    print(v[T][0] // 3)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math

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

g = [[] for _ in range(3*N)]
for a, b in uv:
    g[a-1].append(b-1+N)
    g[a-1+N].append(b-1+2*N)
    g[a - 1 + 2 * N].append(b - 1)

# bfsでよかった
hq = [(0, S-1)]
costs = [math.inf] * 3 * N
while len(hq) > 0:
    c, u = heapq.heappop(hq)
    if u == T - 1:
        print(c // 3)
        sys.exit()
    costs[u] = c
    for v in g[u]:
        if costs[v] > c+1:
            heapq.heappush(hq, (c + 1, v))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
KKP=[[[] for _ in [0]*(N+1)] for _ in [0]*3]
for _ in [0]*M:
    a,b=f()
    KKP[0][a].append(b)
S,T=f()

for j in range(2):
    # j:回数
    for a in range(1,N+1):
        # a:頂点
        for b in KKP[j][a]:
            # KKP[j][a]:aからj+1回でたどり着ける頂点 b
            for c in KKP[0][b]:
                # bから1回でたどり着ける頂点 c
                if not c in KKP[j+1][a]:
                    KKP[j+1][a].append(c)

F=set([])
q=deque()
q.append((S,0))
res=-1
while q:
    node,score=q.popleft()
    if node in F:
        continue
    if T==node:
        res=score
        break
    F.add(node)
    for nnode in KKP[2][node]:
        if nnode in F:
            continue
        q.append((nnode,score+1))
print(res)

Submission status: Time Limit Exceeded

Solution code:
# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
KKP=[[set([]) for _ in [0]*(N+1)] for _ in [0]*3]
for _ in [0]*M:
    a,b=f()
    KKP[0][a].add(b)
S,T=f()

for j in range(2):
    # j:回数
    for a in range(1,N+1):
        # a:頂点
        for b in KKP[j][a]:
             # KKP[j][a]:aからj+1回でたどり着ける頂点
            for c in KKP[0][b]:
                # bから1回でたどり着ける頂点
                KKP[j+1][a].add(c)

F=set([])
q=deque()
q.append((S,0))
res=-1
while q:
    node,score=q.popleft()
    if node in F:
        continue
    if T==node:
        res=score
        break
    F.add(node)
    for nnode in KKP[2][node]:
        if nnode in F:
            continue
        q.append((nnode,score+1))
print(res)

Submission status: Time Limit Exceeded

Solution code:
# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]
for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
    
def check(i):
    res=[i]
    for i in range(3):
        tmpF=set([])
        for r in res:
            for node in G[r]:
                if node in tmpF:
                    continue
                tmpF.add(node)
        res=list(tmpF)
    return res

# KKP=[[]]+[check(i+1) for i in range(N)]

F=set([])
q=deque()
q.append((S,0))
res=-1
while q:
    node,score=q.popleft()
    if node in F:
        continue
    if T==node:
        res=score
        break
    F.add(node)
    for nnode in check(node):
        if nnode in F:
            continue
        q.append((nnode,score+1))
print(res)

Submission status: Time Limit Exceeded

Solution code:
# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]
for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
    
def check(i):
    res=[i]
    for i in range(3):
        tmpF=set([])
        for r in res:
            for node in G[r]:
                if node in tmpF:
                    continue
                tmpF.add(node)
        res=list(tmpF)
    return res

KKP=[[]]+[check(i+1) for i in range(N)]

F=set([])
q=deque()
q.append((S,0))
res=-1
while q:
    node,score=q.popleft()
    if node in F:
        continue
    if T==node:
        res=score
        break
    F.add(node)
    for nnode in KKP[node]:
        if nnode in F:
            continue
        q.append((nnode,score+1))
    if T in F:
        break
print(res)

Submission status: Time Limit Exceeded

Solution code:
# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]
for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
    
def check(i):
    tmpF=[0]*(N+1)
    res=[i]
    for i in range(3):
        tmpres=[]
        tmpF=[0]*(N+1)
        for r in res:
            for node in G[r]:
                if tmpF[node]:
                    continue
                tmpres.append(node)
                tmpF[node]=1
        res=tmpres[:]
    return res

KKP=[[]]+[check(i+1) for i in range(N)]

F=[-1]*(N+1)
F[0]=-1
q=deque()
q.append((S,0))
while q:
    node,par=q.popleft()
    if F[node]>=0:
        continue
    F[node]=F[par]+1
    for nnode in KKP[node]:
        if F[nnode]>=0:
            continue
        q.append((nnode,node))
    if F[T]>=0:
        break
print(F[T])

Submission status: Time Limit Exceeded

Solution code:
# ABC132 E
from collections import deque

f=lambda:map(int,input().split())
N,M=f()
G=[[] for _ in [0]*(N+1)]
for _ in [0]*M:
    a,b=f()
    G[a].append(b)
S,T=f()
    
def check(i):
    tmpF=[0]*(N+1)
    res=[(i,[i])]
    for i in range(3):
        tmpres=[]
        for r,par in res:
            for node in G[r]:
                tmpres.append((node,r))
        res=tmpres[:]
    return list(set([i for i,j in res]))

KKP=[[]]+[check(i+1) for i in range(N)]

F=[-1]*(N+1)
F[0]=-1
q=deque()
q.append((S,0))
while q:
    node,par=q.popleft()
    if F[node]>=0:
        continue
    F[node]=F[par]+1
    for nnode in KKP[node]:
        if F[nnode]>=0:
            continue
        q.append((nnode,node))
    if F[T]>=0:
        break
print(F[T])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from queue import Queue


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    path = defaultdict(list)
    for _ in range(m):
        u, v = map(int, input().split())
        path[u].append(v)
    s, t = map(int, input().split())
    visited = [False] * 110000
    q = Queue()
    q.put((s, 0))
    while not q.empty():
        now, num_move = q.get()
        if visited[now]:
            continue
        for nxt_1 in path[now]:
            for nxt_2 in path[nxt_1]:
                for nxt_3 in path[nxt_2]:
                    if nxt_3 == t:
                        print(num_move + 1)
                        sys.exit()
                    if not visited[nxt_3]:
                        q.put((nxt_3, num_move + 1))
        visited[now] = True
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

from queue import Queue
import numpy as np


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    path = np.matrix([[0] * (n + 1) for _ in range(n + 1)], dtype="i8")
    for _ in range(m):
        u, v = map(int, input().split())
        path[u, v] = 1
    path **= 3
    s, t = map(int, input().split())
    visited = [False] * 110000
    q = Queue()
    q.put((s, 0))
    visited[s] = True
    while not q.empty():
        now, num_move = q.get()
        for nxt in range(1, n + 1):
            if path[now, nxt] == 0:
                continue
            if nxt == t:
                print(num_move + 1)
                sys.exit()
            if not visited[nxt]:
                q.put((nxt, num_move + 1))
                visited[nxt] = True
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

from queue import Queue
import numpy as np


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    path = np.matrix([[0] * (n + 1) for _ in range(n + 1)], dtype="i8")
    for _ in range(m):
        u, v = map(int, input().split())
        path[u, v] = 1
    path **= 3
    s, t = map(int, input().split())
    visited = [False] * 110000
    q = Queue()
    q.put((s, 0))
    while not q.empty():
        now, num_move = q.get()
        if visited[now]:
            continue
        for nxt in range(1, n + 1):
            if path[now, nxt] == 0:
                continue
            if nxt == t:
                print(num_move + 1)
                sys.exit()
            if not visited[nxt]:
                q.put((nxt, num_move + 1))
        visited[now] = True
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from queue import Queue


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    path = defaultdict(list)
    for _ in range(m):
        u, v = map(int, input().split())
        path[u].append(v)
    s, t = map(int, input().split())
    visited = [False] * 110000
    q = Queue()
    q.put((s, 0))
    visited[s] = True
    while not q.empty():
        now, num_move = q.get()
        for nxt_1 in path[now]:
            for nxt_2 in path[nxt_1]:
                for nxt_3 in path[nxt_2]:
                    if nxt_3 == t:
                        print(num_move + 1)
                        sys.exit()
                    if not visited[nxt_3]:
                        q.put((nxt_3, num_move + 1))
        visited[now] = True
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

graph = [[] for i in range(N)]

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

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

from collections import deque
q = deque([])
q.append([S, 0, 0])

seen = set()

while q:
  v,cost,step = q.popleft()
  if step == 0:
    if v == T:
      print(cost)
      break
    if v in seen:
      continue
    seen.add(v)
    cost += 1
    step = 3
  for u in graph[v]:
    q.append([u, cost, step - 1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索

from collections import deque

n, m = map(int, input().split())
g = [set([]) for _ in range(n)]
#隣接リストの作成
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].add(b)

graph = [set([]) for _ in range(n)]
for i in range(n):
    g1 = set([])
    g2 = set([])
    g3 = set([])
    g1 = g1 | g[i]
    for x in g1:
        g2 = g2 | g[x]
    for x in g2:
        g3 = g3 | g[x]
    graph[i] = g3

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

#幅優先探索
q = deque()
level = [-1]*n
q.append(s)
level[s] = 0
while len(q)>0:
    cur = q.popleft()
    lvl = level[cur]
    for i in graph[cur]:
        if level[i]==-1:
            #階層
            level[i] = lvl + 1
            q.append(i)
print(level[t])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索

from collections import deque

n, m = map(int, input().split())
g = [set([]) for _ in range(n)]
#隣接リストの作成
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].add(b)

graph = [set([]) for _ in range(n)]
for i in range(n):
    g1 = set([])
    g2 = set([])
    g3 = set([])
    g1 = g1 | g[i]
    for x in g1:
        g2 = g2 | g[x]
    for x in g2:
        g3 = g3 | g[x]
    graph[i] = g3

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

#幅優先探索
q = deque()
seen = [False]*n
level = [-1]*n
parent = [-1]*n
q.append(s)
seen[s] = True
level[s] = 0
parent[s] = 0
while len(q)>0:
    cur = q.popleft()
    lvl = level[cur]
    for i in graph[cur]:
        if seen[i]==False:
            seen[i] = True
            #階層
            level[i] = lvl + 1
            #親
            parent[i] = cur
            q.append(i)
print(level[t])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

input = sys.stdin.buffer.readline
int1 = lambda x: int(x) - 1
N, M = map(int, input().split())

if M == 0:
    print(-1)
    exit()

UV = np.array([tuple(map(int1, input().split())) for _ in range(M)]) * 3
frm = UV[:, 0].repeat(3) + np.tile(np.arange(3), M)
to = UV[:, 1].repeat(3) + np.tile((np.arange(3) + 1) % 3, M)

S, T = map(int1, input().split())
matr = csr_matrix((np.ones(3 * M, dtype=int), (frm, to)), shape=(3 * N, 3 * N))
way = dijkstra(matr, indices=3 * S)

print(-1 if np.isinf(res := way[3 * T]) else int(res) // 3)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_d(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納　xが根のとき-(サイズ)を格納
        self.par = [-1 for i in range(n)]
        self.n = n

    def find(self, x):
        #根ならその番号を返す
        if self.par[x] < 0:
            return x
        else:
            #親の親は親
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def is_same(self, x, y):
        #根が同じならTrue
        return self.find(x) == self.find(y)

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

        #木のサイズを比較し、小さいほうから大きいほうへつなぐ
        if self.par[x] > self.par[y]:
            x, y = y, x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self, x):
        return -self.par[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.par) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __repr__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = NMI()
    edges = [NLI() for _ in range(M)]
    S, T = NMI()
    tree = make_adjlist_d(N, edges)

    tree = [set(tr) for tr in tree]

    uf = UnionFind(N+1)
    for edge in edges:
        uf.unite(edge[0], edge[1])
    if not uf.is_same(S, T):
        print(-1)
        exit()

    tree2 = [[] for _ in range(N+1)]
    for i in uf.members(S):
        gotos = tree[i]
        for goto in gotos:
            tree2[i] += tree[goto]

    tree2 = [set(tr) for tr in tree2]

    tree3 = [[] for _ in range(N+1)]
    for i in uf.members(S):
        gotos = tree2[i]
        for goto in gotos:
            tree3[i] += tree[goto]

    tree3 = [set(tr) for tr in tree3]

    stack = deque()
    stack.append(S)
    seen = [-1] * (N+1)
    seen[S] = 0
    while stack:
        now = stack.popleft()
        now_step = seen[now]
        for goto in tree3[now]:
            if seen[goto] >= 0:
                continue

            stack.append(goto)
            seen[goto] = now_step + 1

    print(seen[T])



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_d(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


def main():
    N, M = NMI()
    edges = [NLI() for _ in range(M)]
    S, T = NMI()
    tree = make_adjlist_d(N, edges)

    tree = [set(tr) for tr in tree]

    tree2 = [[] for _ in range(N+1)]
    for i in range(1, N+1):
        gotos = tree[i]
        for goto in gotos:
            tree2[i] += tree[goto]

    tree2 = [set(tr) for tr in tree2]

    tree3 = [[] for _ in range(N+1)]
    for i in range(1, N+1):
        gotos = tree2[i]
        for goto in gotos:
            tree3[i] += tree[goto]

    tree3 = [set(tr) for tr in tree3]

    stack = deque()
    stack.append(S)
    seen = [-1] * (N+1)
    seen[S] = 0
    while stack:
        now = stack.popleft()
        now_step = seen[now]
        for goto in tree3[now]:
            if seen[goto] >= 0:
                continue

            stack.append(goto)
            seen[goto] = now_step + 1

    print(seen[T])



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_d(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


def main():
    N, M = NMI()
    edges = [NLI() for _ in range(M)]
    S, T = NMI()
    tree = make_adjlist_d(N, edges)

    tree2 = [[] for _ in range(N+1)]
    for i in range(1, N+1):
        gotos = tree[i]
        for goto in gotos:
            tree2[i] += tree[goto]

    tree2 = [set(tr) for tr in tree2]

    tree3 = [[] for _ in range(N+1)]
    for i in range(1, N+1):
        gotos = tree2[i]
        for goto in gotos:
            tree3[i] += tree[goto]

    tree3 = [set(tr) for tr in tree3]

    stack = deque()
    stack.append(S)
    seen = [-1] * (N+1)
    seen[S] = 0
    while stack:
        now = stack.popleft()
        now_step = seen[now]
        for goto in tree3[now]:
            if seen[goto] >= 0:
                continue

            stack.append(goto)
            seen[goto] = now_step + 1

    print(seen[T])



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def make_adjlist_d(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


def main():
    N, M = NMI()
    edges = [NLI() for _ in range(M)]
    S, T = NMI()
    tree = make_adjlist_d(N, edges)

    tree2 = [[] for _ in range(N+1)]
    for i in range(1, N+1):
        gotos = tree[i]
        for goto in gotos:
            tree2[i] += tree[goto]

    tree3 = [[] for _ in range(N+1)]
    for i in range(1, N+1):
        gotos = tree2[i]
        for goto in gotos:
            tree3[i] += tree[goto]

    tree3 = [set(tr) for tr in tree3]

    stack = deque()
    stack.append(S)
    seen = [-1] * (N+1)
    seen[S] = 0
    while stack:
        now = stack.popleft()
        now_step = seen[now]
        for goto in tree3[now]:
            if seen[goto] >= 0:
                continue

            stack.append(goto)
            seen[goto] = now_step + 1

    print(seen[T])



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

n, m = map(int, input().split())
graph = defaultdict(list)

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


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

q = [s]

pattern = []
cnt = 0

while True:
    for _ in range(3):
        tmp = []
        for x in q:
            tmp = list(set(tmp + graph[x]))
        q = tmp
    cnt += 1
    if t in q:
        print(cnt)
        sys.exit()
    if set(q) in pattern:
        print(-1)
        sys.exit()
    pattern.append(set(q))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

input = sys.stdin.readline
int1 = lambda x: int(x) - 1

N, M = map(int, input().split())

if M == 0:
    print(-1)
    exit()

UV = np.array([tuple(map(int1, input().split())) for _ in range(M)]) * 3
frm = UV[:, 0].repeat(3) + np.tile(np.arange(3), M)
to = UV[:, 1].repeat(3) + np.tile((np.arange(3) + 1) % 3, M)

S, T = map(int1, input().split())
matr = csr_matrix((np.ones(3 * M, dtype=int), (frm, to)), shape=(3 * N, 3 * N))
way = dijkstra(matr, indices=3 * S).astype(int)

res = way[3 * T]
print(res // 3 if res >= 0 else -1)