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:
from collections import defaultdict
from queue import Queue
n, m = list(map(int, input().split()))
MX = int(1e6)
edge = defaultdict(set)
dist = [MX for i in range(n)]
reached = [False for i in range(n)]

for loop in range(m):
    a, b = list(map(int, input().split()))
    edge[a-1].add(b-1)

s, t = list(map(int, input().split()))
s = s-1
t = t-1
dist[s] = 0

q = Queue()
q.put(s)
while not q.empty():
    node = q.get()
    reached[node] = True
    for next_node in edge[node]:
        for nnext_node in edge[next_node]:
            for nnnext_node in edge[nnext_node]:
                if not reached[nnnext_node]: q.put(nnnext_node)
                dist[nnnext_node] = min(dist[nnnext_node], dist[node] + 1)

if dist[t] == MX:
    print(-1)
else:
    print(dist[t])

Submission status: Time Limit Exceeded

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

N,M = map(int,input().split())
S1 = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    S1[u-1].append(v-1)
St,T = map(int,input().split())
S = [[]for i in range(N)]
for i in range(N):
    for k in S1[i]:
        for ken in S1[k]:
            for pa in S1[ken]:
                S[i].append(pa)
D = [float('inf')]*N
D[St-1] = 0
queue = [St-1]
hoge = [0]*N
while queue != []:
    l =0
    for q in queue:
        for i in S[q]:
            if D[i] > D[q]:
                D[i] = D[q]+1
                if not i in hoge[:l]:
                    hoge[l] = i
                    l += 1
    queue = hoge[:l]
if D[T-1] == float('inf'):
    print(-1)
else:
    print(D[T-1])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict

from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

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

graph = defaultdict(set)
for u, v in UV:
    graph[u].add(v)


@lru_cache(maxsize=None)
def dest(v, count):
    if count <= 1:
        return graph[v]
    ret = set()
    for u in graph[v]:
        ret |= dest(u, count - 1)
    return ret


checked = set()
vs = {S}
i = 0
prev = 0
while True:
    i += 1
    s = set()
    for v in vs:
        if v not in checked:
            s |= dest(v, 3)
    checked |= vs
    if T in s:
        print(i)
        break
    if len(checked) == prev:
        print(-1)
        break
    vs = s
    prev = len(checked)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def search(now):   #今いる頂点からけんけんぱでいける点を列挙する
    ret = []
    for v in edge[now]:
        for v2 in edge[v]:
            ret += edge[v2]
    return list(set(ret))

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

edge2 = [search(u) for u in range(N)]

distance = [10**9 for _ in range(N)]
distance[S] = 0

queue = deque([S])
while queue:
    u = queue.popleft()
    for next in edge2[u]:
        if distance[u]+1 < distance[next]:
            distance[next] = distance[u]+1
            queue.append(next)
if distance[T] < 10**9:
    print(distance[T])
else:
    print(-1)

Submission status: Time Limit Exceeded

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]
V = UV[:,1]
S,T = map(int,input().split())
rows = np.concatenate([3*U, 3*U+1, 3*U+2])
cols = np.concatenate([3*V+1, 3*V+2, 3*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: Time Limit Exceeded

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

edges = [set() for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    edges[u-1].add(v-1)

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


step2 = [set() for _ in range(N)]

for u in range(N):
    for v in edges[u]:
        step2[u] |= edges[v]

cost = [-1 for _ in range(N)]
q = []
heapq.heappush(q, (0, S))

while len(q) != 0:
    c, u = heapq.heappop(q)
    if cost[u] != -1:
        continue
    cost[u] = c
    for u2 in step2[u]:
        rms = set()
        for v in edges[u2]:
            if cost[v] != -1:
                rms.add(v)
            else:
                heapq.heappush(q, (c+1, v))

        edges[u2] -= rms

print(cost[T])

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
input=sys.stdin.readline
def main():
  N,M=map(int,input().split())
  G=[set() for i in range(N)]
  for i in range(M):
      u,v=map(int,input().split())
      u,v=u-1,v-1
      G[u].add(v)
  S,T=map(int,input().split())
  A=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          A[i]=A[i] | G[v]
  B=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          B[i]=B[i] | A[v]
  """
  C=[[] for i in range(N)]
  for i in range(N):
      for j in B[i]:
          C[i].append([j,1])
  """
  INF=10**9+7
  def dijkstra(G,s):

    d=[INF]*N
    d[s]=0
    visited={s}
    que=[(0,s)]
    while(que):
      p=heappop(que)
      v=p[1]
      visited.add(v)
      for node in G[v]:
        cost=1
        if (node not in visited) and d[node]>d[v]+cost:
          d[node]=d[v]+cost
          heappush(que,(d[node],node))
    return d
  d=dijkstra(B,S-1)
  if d[T-1]==INF:
    print(-1)
  else:
    print(d[T-1])
if __name__=='__main__':#おまじない
  main()

Submission status: Time Limit Exceeded

Solution code:
#
from collections import deque

import sys
input = sys.stdin.readline


def next_kenp(node, edges, dones):
    nodes = set()
    nodes2 = set()

    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)

    for nn in nodes2:
        for n3 in edges[nn]:
            if n3 in dones or n3 in nodes:
                continue
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = [[] for _ in range(n + 1)]

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

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

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = next_kenp(node, edges, dones)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            que.append((n, step + 1))
            dones.add(n)

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

graph1 = [[] for _ in range(n)]
graph2 = [[] for _ in range(n)]

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


def dfs(v0, v, k):
    if k == 0:
        graph2[v0].append((1, v))
        return

    for i in range(len(graph1[v])):
        dfs(v0, graph1[v][i][1], k-1)

for i in range(n):
    dfs(i, i, 3)
    # print(graph1[i])

for i in range(n):
    graph2[i] = list(set(graph2[i]))
# print()
# for i in range(n):
#     print(graph2[i])


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


from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph2, n, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
INF = 10 ** 12

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

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

vec_ = [[] for _ in range(N)]
for i in range(N) :
    queue = deque([(0, i)])
    while queue :
        step, q = queue.popleft()
        if step == 3 : 
            vec_[i].append(q)
            continue
            
        for j in vec[q] :
            queue.append((step + 1, j))
      
visited = [False] * N
visited[S] = True
queue = deque([(0, S)])
while queue :
    step, q = queue.popleft()
    if q == T : 
        break
    for i in vec_[q] :
        if not visited[i] :
            queue.append((step + 1, i))
            visited[i] = True

if visited[T] :
    print(step)
else :
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import re
from collections import deque
import sys
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_invs(n, mod=DIV):
    inv = [0]*(n+1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, n+1):
        inv[i] = (-(mod//i)*inv[mod % i]) % mod
    return inv

N, M = ints_raw()
graph = [[] for _ in range(N)]
tgraph = [[] for _ in range(N)]

def dfs(u,v,depth):
    if(depth==3):
        tgraph[u].append(v)
        return
    else:
        for nv in graph[v]:
            dfs(u,nv,depth+1)


def main():

    for _ in range(M):
        u,v = ints_raw()
        graph[u-1].append(v-1)
    S,T = [i-1 for i in ints_raw()]
    for n in range(N):
        dfs(n,n,0)
    visited = [-1]*N
    pq = [(0,S)]
    while pq:
        cost,v = heappop(pq)
        if visited[v]!=-1:
            visited[v]=min(visited[v], cost)
        else:
            visited[v] = cost
        for nv in tgraph[v]:
            if(visited[nv]==-1):
                heappush(pq,(cost+1,nv))
    return visited[T]

print(main())

Submission status: Time Limit Exceeded

Solution code:
#
from collections import deque


def next_kenp(node, edges, dones):
    nodes = set()
    nodes2 = set()

    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)

    for nn in nodes2:
        for n3 in edges[nn]:
            if n3 in dones or n3 in nodes:
                continue
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = [[] for _ in range(n + 1)]

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

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

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = next_kenp(node, edges, dones)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            que.append((n, step + 1))
            dones.add(n)

    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    for _ in range(M):
        u,v = MI_()
        edge[u].append(v)
    S, T = MI_()

    edge2 = [[] for _ in range(N)]
    for sor in range(N):
        queue = [sor]
        for _ in range(3):
            tmp = set()
            while queue:
                now = queue.pop()
                for to in edge[now]:
                    tmp.add(to)
            queue = tmp
        edge2[sor] = queue

    #print(*edge2,sep="\n")

    queue = [S]
    checked = set()
    for i in range(1,max(N,M+2)):
        tmp = set()
        while queue:
            s = queue.pop()
            for to in edge2[s]:
                if to == T:
                    print(i)
                    exit()
                else:
                    if to not in checked:
                        tmp.add(to)
                        checked.add(to)
        queue = tmp
    print(-1)
            

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def f(n,m):
    to = {}
    rv = {}
    for _ in range(m):
        u, v = map(int, input().split())
        to.setdefault(u, [])
        to[u] += [v]
        rv.setdefault(v, [])
        rv[v] += [u]
    s, t = map(int, input().split())

    ss = set()
    ss.add(s)
    gs = set()
    gs.add(t)
    vst1 = set()
    vst2 = set()
    cnt = 0

    while 1:
        cnt += 1
        for _ in range(3):
            nss = set()
            for i in ss:
                if i not in to: continue
                for j in to[i]:
                    nss.add(j)
            ss = nss
        if ss & gs:
            print(cnt)
            exit()
        if ss <= vst1:
            print(-1)
            exit()
        vst1 |= ss

        cnt += 1
        for _ in range(3):
            ngs = set()
            for i in gs:
                if i not in rv: continue
                for j in rv[i]:
                    ngs.add(j)
            gs = ngs
        if ss & gs:
            print(cnt)
            exit()
        if gs <= vst2:
            print(-1)
            exit()
        vst2 |= gs

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

Submission status: Time Limit Exceeded

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.9:
        print(-1)
        sys.exit()

else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
f =[]
N = 0
def dfs_tri(t, u):
    global f
    global N
    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]):
                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(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: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**9)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,m = na()
d = [[] for i in range(n)]

for i in range(m):
    u,v = na()
    d[u-1].append(v-1)

s,t = na()
s-=1
t-=1

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

def dfs(a,k):
    for p in d[a]:
        for q in d[p]:
            for r in d[q]:
                if g[r] >= 0 and g[r] < k+1:
                    break
                g[r] = k+1
                dfs(r,k+1)

dfs(s,0)
print(g[t])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
u,v=[],[]
path=[[] for i in range(n)]
for i in range(m):
    ui,vi=[int(x)-1 for x in input().split()]
    path[ui].append(vi)
    # path[vi].append(ui)
s,t=[int(x)-1 for x in input().split()]
from collections import deque
q=deque()
q.append((s,0))
# print(path)
check=[False]*n
while q:
    # print(q)
    p,num=q.popleft()
    if num%3!=0:
        for i in path[p]:
            q.append((i,num+1))
        continue
    elif p==t:
        print(num//3)
        import sys
        sys.exit()
    elif check[p]==True:
        continue
    else:
        for i in path[p]:
            q.append((i,num+1))
        check[p]=True
print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]

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

    converted_edges = [[] for _ in range(N)]
    for v, v_edge in enumerate(edges):
        three_steps_nodes = []
        for w in edges[v]:
            for x in edges[w]:
                for y in edges[x]:
                    three_steps_nodes.append(y)
        converted_edges[v] = three_steps_nodes[:]

    S, T = map(lambda x: int(x) - 1, input().split())
    q = deque([(S, 0)])

    nodes = [-1] * N

    while q:
        cv, count = q.popleft()
        if cv == T:
            if nodes[cv] == -1:
                nodes[cv] = count
            else:
                nodes[cv] = min(nodes[cv], count)
        else:
            if nodes[cv] == -1 or count < nodes[cv]:
                nodes[cv] = count
                for u in converted_edges[cv]:
                    q.append((u, count + 1))

    print(nodes[T])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
to={}
rv={}
for _ in range(m):
    u,v=map(int,input().split())
    to.setdefault(u,[])
    to[u]+=[v]
    rv.setdefault(v, [])
    rv[v] += [u]
s,t=map(int,input().split())

ss=set()
ss.add(s)
gs=set()
gs.add(t)
vst1=set()
vst2=set()
cnt=0

while 1:
    cnt+=1
    for _ in range(3):
        nss=set()
        for i in ss:
            if i not in to:continue
            for j in to[i]:
                nss.add(j)
        ss=nss
    if ss&gs:
        print(cnt)
        exit()
    if ss<=vst1:
        print(-1)
        exit()
    vst1|=ss

    cnt+=1
    for _ in range(3):
        ngs=set()
        for i in gs:
            if i not in rv:continue
            for j in rv[i]:
                ngs.add(j)
        gs=ngs
    if ss&gs:
        print(cnt)
        exit()
    if gs<=vst2:
        print(-1)
        exit()
    vst2|=gs

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
visited = [[False,False,False] for _ in range(n)]
ren = [[0]*n for _ in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    ren[u-1][v-1] = 1
s,t = map(int,input().split())

Q = [(s,0)]
visited[s-1][2]=True
ans = -1

while len(Q)>0:
    curs,curcount = Q.pop(0)
    if curs == t:
        ans = curcount
        break
    for i in range(n):
        if ren[curs-1][i] and not visited[i][0]:
            visited[i][0]=True
            for j in range(n):
                if ren[i][j] and not visited[j][1]:
                    visited[j][1]=True
                    for k in range(n):
                        if ren[j][k] and not visited[k][2]:
                            visited[k][2]=True
                            Q.append((k+1,curcount+1))

print(ans)

Submission status: Time Limit Exceeded

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

graph_ken = [[]]
for i in range(1, N+1):
    now = i
    queue = graph[now][:]
    for _ in range(2):
        nextqueue = []
        for next in queue:
            nextqueue.extend(graph[next])
        queue = f7(nextqueue)
    graph_ken.append(queue)



queue = [S]
visit = [False]*(N+1)
ans = 0
while len(queue) > 0:
    nextqueue = []
    for now in queue:
        if visit[now]:
            continue
        visit[now] = True
        for next in graph_ken[now]:
            if not visit[next]:
                nextqueue.append(next)
    queue = f7(nextqueue)
    if visit[T]:
        break
    ans += 1

if visit[T]:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict


def solve(N: int, M: int, U: "List[int]", V: "List[int]", S: int, T: int):
    S -= 1
    T -= 1
    adj = [[] for i in range(N)]
    for u, v in zip(U, V):
        adj[u-1].append(v-1)
    Q = [(0, S, frozenset([S]))]
    visited = defaultdict(lambda: 0)

    while len(Q) > 0:
        d, u, route = heapq.heappop(Q)
        if u == T:
            visited[route] += 1
        if u == T and d % 3 == 0:
            print(d // 3)
            return
        if u == T and visited[route] >= 3:
            print(-1)
            return
        for v in adj[u]:
            heapq.heappush(Q, (d+1, v, route | {v}))

    print(-1)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    u = [int()] * (M)  # type: "List[int]" 
    v = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    S = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    solve(N, M, u, v, S, T)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
input=sys.stdin.readline
def main():
  N,M=map(int,input().split())
  G=[set() for i in range(N)]
  for i in range(M):
      u,v=map(int,input().split())
      u,v=u-1,v-1
      G[u].add(v)
  S,T=map(int,input().split())
  A=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          A[i]=A[i] | G[v]
  B=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          B[i]=B[i] | A[v]
  C=[[] for i in range(N)]
  for i in range(N):
      for j in B[i]:
          C[i].append([j,1])
  INF=10**9+7
  def dijkstra(G,s):

    d=[INF]*N
    d[s]=0
    visited={s}
    que=[(0,s)]
    while(que):
      p=heappop(que)
      v=p[1]
      visited.add(v)
      for node,cost in G[v]:
        if (node not in visited) and d[node]>d[v]+cost:
          d[node]=d[v]+cost
          heappush(que,(d[node],node))
    return d
  d=dijkstra(C,S-1)
  if d[T-1]==INF:
    print(-1)
  else:
    print(d[T-1])
if __name__=='__main__':#おまじない
  main()

Submission status: Time Limit Exceeded

Solution code:
#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def next_kenp(node, edges, dones):
    nodes = set()
    nodes2 = set()

    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)

    for nn in nodes2:
        for n3 in edges[nn]:
            if n3 in dones or n3 in nodes:
                continue
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = [[] for _ in range(n + 1)]

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

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

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = next_kenp(node, edges, dones)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            if n not in dones:
                que.append((n, step + 1))
                dones.add(n)
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, collections

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    son = [[] for i in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        son[u-1].append(v-1)
    S, T = map(int, input().split())

    graphB = [set() for i in range(N)] 
    for i in range(N):
        for s1 in son[i]:
            for s2 in son[s1]:
                graphB[i] |= set(son[s2])
    
    q = collections.deque()
    visited = [-1] * N
    q.append((0, S-1))
    while q:
        cost, now = q.popleft()
        if visited[now] == -1:
            visited[now] = cost
            for s in graphB[now]:
                if visited[s] == -1: q.append((cost + 1, s))

    print(visited[T-1])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
UV = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
S,T = map(lambda x:int(x)-1,input().split())

es = [[set() for j in range(N)] for i in range(3)]
for u,v in UV:
    es[0][u].add(v)

for i in range(2):
    for j in range(N):
        for k in es[i][j]:
            es[i+1][j] |= es[0][k]

INF = float('inf')
dist = [INF]*N
dist[S] = 0
q = deque([S])
while q:
    v = q.popleft()
    for to in es[2][v]:
        if dist[to] != INF: continue
        dist[to] = dist[v]+1
        if to == T:
            print(dist[to])
            exit()
        q.append(to)

print(-1)

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N, M = MI()
    edge = [[] for _ in range(N)]
    for _ in range(M):
        u,v = MI_()
        edge[u].append(v)
    S, T = MI_()

    def dfs(now, cnt,ends):
        if cnt == 3:
            ends.append(now)
            return 
        for to in edge[now]:
            #print(cnt,now,to)
            dfs(to, cnt + 1,ends)
            


    edge2 = [[] for _ in range(N)]
    for sor in range(N):
        queue = [sor]
        for _ in range(3):
            tmp = set()
            while queue:
                now = queue.pop()
                for to in edge[now]:
                    tmp.add(to)
            queue = tmp
        edge2[sor] = queue

    #print(*edge2,sep="\n")

    queue = [S]
    checked = set()
    for i in range(1,M+2):
        tmp = set()
        while queue:
            s = queue.pop()
            for to in edge2[s]:
                if to == T:
                    print(i)
                    exit()
                else:
                    if to not in checked:
                        tmp.add(to)
                        checked.add(to)
        queue = tmp
    print(-1)
            

if __name__ == '__main__':
    main()