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 queue
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, V):
    color = [WHITE for i in range(N+1)]
    d = [INFTY for i in range(N+1)]
    d[s] = 0
    q = queue.Queue()
    q.put(s)

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

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

    return d

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

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

Submission status: Time Limit Exceeded

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

uv = {}
for i in range(M):
    u, v = map(int, input().split())
    if not u in uv:
        uv[u] = [v]
    else:
        uv[u].append(v)


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

b = [False] * (10**5+1)
us = [S]
b[S] = True
cnt = 0
while us:
    cnt += 1
    for i in range(3):
        tmpus = []
        for u in us:
            if u in uv:
                for v in uv[u]:
                    tmpus.append(v)
        us = tmpus

    if T in us:
        print(cnt)
        break

    tmpus = []
    for u in us:
        if b[u] is False:
            b[u] = True
            tmpus.append(u)
    us = tmpus


if not T in us:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        dp[0][v-1].append(u-1)
    S, T = map(int, input().split())
    for i in range(1, 3):
        for j in range(N):
            tmp = list()
            for nxt in dp[i-1][j]:
                tmp += dp[0][nxt]
            if len(tmp):
                dp[i][j] = list(set(tmp))
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in dp[2][i]:
            adj[j].add(i)
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


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].union(G[v])
  B=[set() for i in range(N)]
  for i in range(N):
      for v in G[i]:
          B[i]=B[i].union(A[v])
  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


def main():
    N, M = map(int, input().split())
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        dp[0][v-1].append(u-1)
    S, T = map(int, input().split())
    for i in range(1, 3):
        for j in range(N):
            tmp = list()
            for nxt in dp[i-1][j]:
                tmp += dp[0][nxt]
            dp[i][j] = set(tmp)
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in dp[2][i]:
            adj[j].add(i)
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}


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

cos = [[] for _ in range(n)]
for _ in range(m):
    x,y = map(int,input().split())
    cos[x-1].append(y-1) #x→y という辺

cost = [[float("inf") for _ in range(n)] for _ in range(n)]

def conn(i,j):
    for k in cos[i]:
        for l in cos[k]:
            if j in cos[l]:
                cost[i][j] =1

for i in range(n):
    for j in range(n):
        conn(i,j)

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

def solve():
    d = [float("inf")]*n
    used = [False] * n
    d[s-1] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j],d[v]+cost[v][j])
    if d[t-1] == float("inf"):
        d[t-1] = -1
    print(d[t-1])
    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
        def dump(*args):
            names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
            print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
    except:
        def dump(*args):
            pass

    solve()

# vim: set foldmethod=marker:}}}

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ 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

    new_graph = [set() for _ in range(n)]
    for i in range(n):
        for child in graph[i]:
            for grandchild in graph[child]:
                for greatgrandchild in graph[grandchild]:
                    new_graph[i].add(greatgrandchild)

    q = new_graph[s]
    visited = [False] * n
    visited[s] = True

    cnt = 1
    while t not in q:
        new_q = set()
        for qi in q:
            if not visited[qi]:
                visited[qi] = True
                for child in new_graph[qi]:
                    if not visited[child]:
                        new_q.add(child)
        q = new_q
        cnt += 1
        if cnt == n + 1:
            print(-1)
            return

    print(cnt)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush, heappop

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

visited = [False] * N
visited[S] = True
queue_ = [(0, S)]

while queue_ :
    cost, i = heappop(queue_)
    
    queue = deque([(0, i)])
    while queue :
        step, q = queue.popleft()
        if step == 2 : 
            for j in vec[q] :
                if j == T :
                    print(cost + 1)
                    exit()
                if not visited[j] :
                    visited[j] = True
                    heappush(queue_, (cost + 1, j))
        else :
            for j in vec[q] :
                queue.append((step + 1, j))

print(-1)

Submission status: Time Limit Exceeded

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

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

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


par = [i for i in range(3*N)]
par2 = [-1 for i in range(3*N)]
rank = [0 for i in range(3*N)]

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def same(x, y):
    return find(x) == find(y)

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

ans = 0
start = [S-1]
frag = 1
g = -1
while frag:
    frag = 0
    ans += 1
    g += 1
    g %= 3
    l = len(start)
    for i in range(l):
        s = start.pop(0)
        if par2[s + g * N] == 1:
            continue
        par2[s + g * N] == 1
        for j in range(len(G[s])):
            start.append(G[s][j])
            if g == 2:
                if same(s + 2 * N, G[s][j]):
                    continue
                else:
                    frag = 1
                    unite(s + 2 * N, G[s][j])

            else:
                if same(s + g * N, G[s][j] + (g+1) * N):
                    continue
                else:
                    frag = 1
                unite(s+ g * N, G[s][j] + (g+1) * N)

        if same(S-1, T-1) and par[S-1] != -1:
            print(ans//3)
            sys.exit()
print(-1)

Submission status: Time Limit Exceeded

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([S])
que1, que2, nque = set(), set(), set()
ans = 0

while T not in que and len(que) != 0:
    que -= pque
    pque |= que
    
    for s in que:
        que1 |= G[s-1]
    for s in que1:
        que2 |= G[s-1]
    for s in que2:
        nque |= G[s-1]

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ 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

    new_graph = [set() for _ in range(n)]
    for i in range(n):
        for child in graph[i]:
            for grandchild in graph[child]:
                for greatgrandchild in graph[grandchild]:
                    new_graph[i].add(greatgrandchild)

    q = new_graph[s]
    visited = [False] * n
    visited[s] = True

    cnt = 1
    while t not in q:
        new_q = set()
        for qi in q:
            if not visited[qi]:
                visited[qi] = True
                for child in new_graph[qi]:
                    new_q.add(child)
        q = new_q
        cnt += 1
        if cnt == n + 1:
            print(-1)
            return

    print(cnt)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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

from heapq import heappop, heappush
prev = [-1 for _ in range(n+1)]
def dijkstra(s, graph):
  d = [float("INF") for _ in range(n+1)]
  d[s] = 0
  q = []
  heappush(q, [0, s])

  while q:
    dt, v = heappop(q)
    if d[v] < dt:
      continue
    for to in graph[v]:
      if d[to] > dt+1:
        d[to] = dt+1
        prev[to] = v
        heappush(q, [d[to], to])
  return d
dd = dijkstra(s, d2)
if dd[t]==float("INF"):
  print(-1)
else:
  print(dd[t])

Submission status: Time Limit Exceeded

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

pa = [True]*(N+1)
pa2 = [True]*(N+1)
cnt = 0

nowS = [S]
nowT = [T]

flag = False

while True:
    cnt += 1
    a = []
    for i in nowS:
        for j in uv[i]:
            a.append(j)
    b = []
    for i in a:
        for j in uv[i]:
            b.append(j)
    nowS = []
    for i in b:
        for j in uv[i]:
            if pa[j]:
                nowS.append(j)
                pa[j] = False
    
    for i in nowS:
        if i in nowT:
            flag = True
    
    if flag:
        print(cnt)
        break

    if len(nowS) == 0:
        print(-1)
        break
    

    cnt += 1
    a = []
    for i in nowT:
        for j in vu[i]:
            a.append(j)
    b = []
    for i in a:
        for j in vu[i]:
            b.append(j)
    nowT = []
    for i in b:
        for j in vu[i]:
            if pa2[j]:
                nowT.append(j)
                pa2[j] = False
    
    for i in nowT:
        if i in nowS:
            flag = True
    
    if flag:
        print(cnt)
        break

    if len(nowS) == 0:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ 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

    new_graph = [set() for _ in range(n)]
    for i in range(n):
        for child in graph[i]:
            for grandchild in graph[child]:
                for greatgrandchild in graph[grandchild]:
                    new_graph[i].add(greatgrandchild)

    q = new_graph[s]
    visited = [False] * n
    visited[s] = True

    cnt = 1
    while t not in q:
        new_q = set()
        for qi in q:
            for child in new_graph[qi]:
                new_q.add(child)
        q = new_q
        cnt += 1
        if cnt == n + 1:
            print(-1)
            return

    print(cnt)


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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, kkp_cnt))

    if dest_t:
        break

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([{s},{0}])
    n*=3
    ans=0
    while n:
        tmp=set()
        p=w.pop()
        if 0 in p:
            n-=1
            ans+=1
            w.appendleft(p)
        else:
            for i in p:
                if i in d:
                    for j in d[i]:
                        tmp.add(j)
            if t in tmp and ans%3==0:
                print(ans//3)
                exit()
            w.appendleft(tmp)
    print(-1)

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    dp = [[set() for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        dp[0][v-1].add(u-1)
    S, T = map(int, input().split())
    for i in range(1, 3):
        for j in range(N):
            tmp = set()
            for nxt in dp[i-1][j]:
                tmp = tmp.union(dp[0][nxt])
            dp[i][j] = tmp
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in dp[2][i]:
            adj[j].add(i)
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（Dijkstra法）
def Dijkstra(adjList, vSt, vEn):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if vNow == vEn: break
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2, wt in adjList[vNow]:
            c2 = cNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))
    return costs


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

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

adjL0 = [set() for _ in range(N)]
for u, v in edges:
    for v0 in v0s[u]:
        for v2 in v2s[v]:
            adjL0[v0].add((v2, 1))

adjL = [[] for _ in range(N)]
for v, adj in enumerate(adjL0):
    adjL[v] = list(adj)

costs = Dijkstra(adjL, S, T)

if costs[T] == INF:
    print(-1)
else:
    print(costs[T])

Submission status: Time Limit Exceeded

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

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

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

#print(link)

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

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

    # s = [1] とか s = [1,2,3]
    res = set()
    for i in range(len(link[s])):
        res.update(hop(link[s][i], n - 1))

    return res

import collections
cur = collections.deque([])

cur.append((s,0))
hops = []
while len(cur) != 0:
    x = cur.popleft()
    next, hopcount = x[0], x[1]
    r = hop(next, 3)
    r = list(r)
    #print(r)

    for i in range(len(r)):
        if r[i] == t:
            hops.append(hopcount + 1)
        cur.append( (r[i], hopcount + 1) )


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

Submission status: 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)
edge2 = defaultdict(set)
kenedge = 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)

for i in range(n):
    step1 = set()
    for ii in edge[i]:
        edge2[i] |= edge[ii]

for i in range(n):
    step2 = set()
    for ii in edge2[i]:
        kenedge[i] |= edge[ii]

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 kenedge[node]:
        if not reached[next_node]: q.put(next_node)
        dist[next_node] = min(dist[next_node], dist[node] + 1)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    N, M = map(int, input().split())
    dp = [[set() for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        dp[0][v-1].add(u-1)
    S, T = map(int, input().split())
    for i in range(1, 3):
        for j in range(N):
            tmp = list()
            for nxt in dp[i-1][j]:
                tmp += list(dp[0][nxt])
            dp[i][j] = set(tmp)
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in dp[2][i]:
            adj[j].add(i)
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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)
    if RD[q] == -1:
      continue
    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)