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,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v)
s,t = inm()
s -= 1
t -= 1

reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]
def mark(f):
    x = []
    for v1 in dst[f]:
        for v2 in dst[v1]:
            for v3 in dst[v2]:
                if v3 == f:
                    continue
                x.append(v3)
    reach3[f] = list(set(x))
    m3done[f] = True

dist = [-1] * n
dist[s] = 0
q = deque([(s,0)])
while len(q)>0:
    v,d = q.popleft()
    if not m3done[v]:
        mark(v)
    for nxt in reach3[v]:
        if dist[nxt] > -1:
            continue
        if nxt==t:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v)
s,t = inm()
s -= 1
t -= 1

reach3 = [ [] for i in range(n) ]
def mark(f):
    x = []
    for v1 in dst[f]:
        for v2 in dst[v1]:
            for v3 in dst[v2]:
                if v3 == f:
                    continue
                x.append(v3)
    reach3[f] = list(set(x))

for v in range(n):
    mark(v)

dist = [-1] * n
dist[s] = 0
q = deque([(s,0)])
while len(q)>0:
    v,d = q.popleft()
    for nxt in reach3[v]:
        if dist[nxt] > -1:
            continue
        if nxt==t:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy

N,M = map(int,input().split())
G = [set() for i in range(N)]
G3 = [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 = {S}
que = {S}
nque = set()
ans = 0

for i in range(N):
    for s in G[i]:
        nque |= G[s-1]
    for s in nque:
        G3[i] |= G[s-1]
    if S in G3[i]:  G3[i].remove(S)
    nque = set()

while T not in que and len(que) != 0:
    for s in que:
        for t in G3[s-1]:
            if t not in pque:
                nque.add(t)
                pque.add(t)

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

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

Submission status: Time Limit Exceeded

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

n,k = m()

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

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

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

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if min(sss[now][nn],coun) != Max:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)

Submission status: Time Limit Exceeded

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

n,k = m()

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

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

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

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if min(sss[now][nn],coun) == coun:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
G = [set() for i in range(N)]
G3 = [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 = {S}
que = {S}
nque = set()
ans = 0

for i in range(N):
    for s in G[i]:
        nque |= G[s-1]
    for s in nque:
        G3[i] |= G[s-1]
    G3[i] -= {S}
    nque = set()

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

    pque |= que
    que = nque - pque
    nque = set()
    ans += 1

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

Submission status: Time Limit Exceeded

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

n,k = m()

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

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

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

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,g,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,st,co
    if min(sss[now][nn],coun) == coun:
        if nn == 0 and st == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.appendleft([x,nn,i,coun])
    else:
        if now == st and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)

Submission status: Time Limit Exceeded

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

n,k = m()

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

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

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

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,g,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,st,co
    if min(sss[now][nn],coun) == coun:
        if nn == 0 and st == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == st and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)

Submission status: Time Limit Exceeded

Solution code:
import queue

N,M = map(int, input().split())
G = [[] for i in range(3*N+1)]

for i in range(M):
  u,v = map(int, input().split())
  G[u].append(v+N)
  G[u+N].append(v+2*N)
  G[u+2*N].append(v)
S,T = map(int, input().split())

def bfs(s):
  que = queue.Queue()
  que.put(s)
  d = [-1 for _ in range(3*N+1)]
  d[s] = 0

  while not que.empty():

    p = que.get()
    if (T == p):
      return d[p]

    for pp in G[p]:
      if d[pp] == -1:
        que.put(pp)
        d[pp] = d[p]+1

  return -1

ans = bfs(S)
if (-1 == ans):
  print(-1)
else:
  print(ans//3)

Submission status: Time Limit Exceeded

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
s,t=map(int,input().split())
check=[0]*(n+1)
q=collections.deque()
q.append([s,0])
ans=0
while len(q)!=0:
  v,c=q.popleft()
  if v==t:
    ans=c
    break
  for i in g[v]:
    for j in g[i]:
      for k in g[j]:
        if check[k]==0:
          q.append([k,c+1])
          check[k]=1
if ans==0:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)

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

    f = []
    for i in range(n):
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        f.append(b)

    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        if t in f[i]:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(f[i])]
    return -1


print(BC132_E())

Submission status: Time Limit Exceeded

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

n,k = m()

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

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

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

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

while eee:
    op = eee.pop()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)

Submission status: Time Limit Exceeded

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

def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     que=[s]
     ok=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if j not in ok:
                         ok.append(j)
                         if j==t:
                              return cnt//3
                         que2.append(j)
          que=que2
     return -1

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
def main():
    input = sys.stdin.readline
    N, M = map(int,input().split())
    G = [[[],[],[]] for k in range(N)]

    for k in range(M):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        G[u][0] += [v]
        G[u][1] += [v]
        G[u][2] += [v]

    S, T = map(int,input().split())
    S -= 1
    T -= 1
    D1 = [[200000,200000,200000] for k in range(N)]
    D1[S][0] = 0
    def dfs1(now, dist):
        for tsugi in G[now][1]:
            if D1[tsugi][1] > dist + 1:
                D1[tsugi][1] = dist + 1
                dfs2(tsugi, dist+1)
    def dfs2(now, dist):
        for tsugi in G[now][2]:
            if D1[tsugi][2] > dist + 1:
                D1[tsugi][2] = dist + 1
                dfs3(tsugi, dist+1)
    def dfs3(now, dist):
        for tsugi in G[now][0]:
            if D1[tsugi][0] > dist + 1:
                D1[tsugi][0] = dist + 1
                dfs1(tsugi, dist+1)

    dfs1(S,0)

    if D1[T][0]%3 == 0:
        print(D1[T][0]//3)
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
nodes = [[] for i in range(N)]

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

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

num = s
step = 0
q = [[num, step]]
check = [[False for i in range(N)] for j in range(3)]
ok = False
while len(q) > 0:
    num, step = q.pop(0)
    tmp = step % 3
    if check[tmp][num]:
        continue
    if tmp == 0 and num == t:
        print(step//3)
        ok = True
        break
    for next in nodes[num]:
        check[tmp][num] = True
        q.append([next, step+1])
if not ok:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import queue

N,M = map(int, input().split())
dst = [[] for i in range(N+1)]

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

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

for i in range(1,N+1):
  for s0 in dst[i]:
    for s1 in dst[s0]:
      for s2 in dst[s1]:
        if i != s2:
          if not s2 in dst2[i]:
            dst2[i].append(s2)
  
def bfs(s):
  que = queue.Queue()
  que.put(s)
  d = [-1 for _ in range(N+1)]
  d[s] = 0

  while not que.empty():

    p = que.get()
    if (T == p):
      return d[p]

    for pp in dst2[p]:
      if d[pp] == -1:
        que.put(pp)
        d[pp] = d[p]+1

  return -1

ans = bfs(S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import defaultdict, deque
import math
from math import factorial
import re

def walk(edges, S, T):
    triple_edges = defaultdict(set)
    for u, vs in edges.items():
        for v in vs:
            triple_edges[(u, 0)].add((v, 1))
            triple_edges[(u, 1)].add((v, 2))
            triple_edges[(u, 2)].add((v, 0))

    current_nodes = deque([((S, 0), 0)])
    visited = set()
    while current_nodes:
        node, step = current_nodes.popleft()

        if not node in triple_edges:
            continue

        step += 1
        visited.add(node)

        next_nodes = triple_edges[node]

        for next_node in next_nodes:
            if next_node == (T, 0):
                return step // 3
            if not next_node in visited:
                current_nodes.append((next_node, step))

    return -1

def main():
    edges = defaultdict(set)
    N, M = map(int, input().split())
    for i in range(M):
        u, v = map(int, input().split())
        edges[u].add(v)
    S, T = map(int, input().split())

    step = walk(edges, S, T)
    print(step)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

N, M = map(int,input().split())
G = [[[],[],[]] for k in range(N)]

for k in range(M):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    G[u][0] += [v]
    G[u][1] += [v]
    G[u][2] += [v]

S, T = map(int,input().split())
S -= 1
T -= 1
D1 = [[200000,200000,200000] for k in range(N)]
D1[S][0] = 0
def dfs1(now, dist):
    for tsugi in G[now][1]:
        if D1[tsugi][1] > dist + 1:
            D1[tsugi][1] = dist + 1
            dfs2(tsugi, dist+1)
def dfs2(now, dist):
    for tsugi in G[now][2]:
        if D1[tsugi][2] > dist + 1:
            D1[tsugi][2] = dist + 1
            dfs3(tsugi, dist+1)
def dfs3(now, dist):
    for tsugi in G[now][0]:
        if D1[tsugi][0] > dist + 1:
            D1[tsugi][0] = dist + 1
            dfs1(tsugi, dist+1)

dfs1(S,0)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
     n,m=map(int,input().split())
     field=[[] for i in range(3*n)]
     for i in range(m):
          x,y=map(int,input().split())
          x,y=x-1,y-1
          field[3*x].append(3*y+1)
          field[3*x+1].append(3*y+2)
          field[3*x+2].append(3*y)
     
     s,t=map(int,input().split())
     s,t=s-1,t-1
     s,t=3*s,3*t
     
     que=[s]
     ok=[s]
     cnt=0
     while que!=[]:
          que2=[]
          cnt+=1
          for i in que:
               for j in field[i]:
                    if j not in ok:
                         ok.append(j)
                         if j==t:
                              return cnt//3
                         que2.append(j)
          que=que2
     return -1

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
field=[[] for i in range(3*n)]
for i in range(m):
     x,y=map(int,input().split())
     x,y=x-1,y-1
     field[3*x].append(3*y+1)
     field[3*x+1].append(3*y+2)
     field[3*x+2].append(3*y)

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

que=[s]
ok=[s]
cnt=0
flag=0
while que!=[] and flag==0:
     que2=[]
     cnt+=1
     for i in que:
          if flag==1:
               break
          for j in field[i]:
               if j not in ok:
                    ok.append(j)
                    if j==t:
                         print(cnt//3)
                         flag=1
                         break
                    que2.append(j)
     que=que2
if flag==0:
     print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = [ int(v) for v in input().split() ]
connect_list = [[] for j in range(n)]
new_connect_list = [[] for j in range(n)]
start_list = []
for i in range(m):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append(b)
    start_list.append(a)
s, t = [ int(v)-1 for v in input().split() ]

for i in start_list:
    point_list = [i]
    for j in range(3):
        new_point_list = []
        for k in point_list:
            new_point_list += connect_list[k]
        point_list = new_point_list
    new_connect_list[i] += point_list
new_connect_list = [ list(set(i)) for i in new_connect_list]

ans = -1
point_list = [s]
visited_point_list = set(point_list)
time = 0
while point_list != []:
    time += 1
    new_point_list = []
    for j in point_list:
        for k in new_connect_list[j]:
            if k not in visited_point_list:
                new_point_list.append(k)
                visited_point_list.add(k)
    new_point_list = list(set(new_point_list))
    point_list = new_point_list

    if t in point_list:
        ans = time
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
field=[[] for i in range(3*n)]
for i in range(m):
     x,y=map(int,input().split())
     x,y=x-1,y-1
     field[3*x].append(3*y+1)
     field[3*x+1].append(3*y+2)
     field[3*x+2].append(3*y)

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

que=[s]
ok=[s]
cnt=0
flag=0
while que!=[]:
     que2=[]
     cnt+=1
     for i in que:
          if flag==1:
               break
          for j in field[i]:
               if j not in ok:
                    ok.append(j)
                    if j==t:
                         print(cnt//3)
                         flag=1
                         break
                    que2.append(j)
     que=que2
if flag==0:
     print(-1)

Submission status: Time Limit Exceeded

Solution code:
def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        if t in b:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(b - visited)]
    return -1


print(BC132_E())

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
uv = [[] for ni in range(n)]
for i in range(m):
  u,v = map(lambda x:int(x)-1,input().split())
  uv[u].append(v)
s,t = list(map(lambda x:int(x)-1,input().split()))
flag = 0
time = 0
a = [set() for ni in range(n)]
a[s].add(0)
while time < 3*n:
  time += 1
  ad = []
  for ni in range(n):
    ad.append(set(map(lambda x:x+1,a[ni])))
  for ni in range(n):
    luv = len(uv[ni])
    for luvi in range(luv):
      a[uv[ni][luvi]] |= ad[ni]
  for x in a[t]:
    if x%3 == 0:
      flag = 1
      ans = x//3
  if flag == 1:
    break
if flag==0:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        stack += [(x, d + 1) for x in list(b - visited)]
    return -1


print(BC132_E())

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
field=[[] for i in range(3*n)]
for i in range(m):
     x,y=map(int,input().split())
     x,y=x-1,y-1
     field[3*x].append(3*y+1)
     field[3*x+1].append(3*y+2)
     field[3*x+2].append(3*y)

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

que=[s]
ok=[s]
cnt=0
flag=0
while que!=[]:
     que2=[]
     cnt+=1
     for i in que:
          for j in field[i]:
               if j not in ok:
                    ok.append(j)
                    if j==t:
                         print(cnt//3)
                         flag=1
                         break
                    que2.append(j)
     que=que2
if flag==0:
     print(-1)

Submission status: Time Limit Exceeded

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

n,k = m()

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

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

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

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

while eee:
    op = eee.pop()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)

Submission status: Time Limit Exceeded

Solution code:
def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        stack += [(x, d + 1) for x in list(b)]
    return -1


print(BC132_E())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def kkp(array: np.ndarray, s):
    dst = array[array[:,0]==s,1]
    return list(dst)

def kkp3(steplist, idx):
    dst = []
    state = idx

    state = steplist[state]
    temp = []
    for s1 in state:
        temp.extend(steplist[s1-1])
    state = list(set(temp))
    temp = []
    for s1 in state:
        temp.extend(steplist[s1-1])
    state = list(set(temp))
    return state


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

uv_np = np.asarray(uv)

if m == 0:
    flag = False
else:

    steplist = []*n

    steplist = [kkp(uv_np, i+1) for i in range(n)]
    kkplist = [kkp3(steplist, i) for i in range(n)]

    cnt = 0
    flag = True
    state = [s]
    check = [s]

while flag:
    cnt += 1
    temp = []
    for s in state:
        temp.extend(kkplist[s-1])
    state = list(set(temp))
    if t in state:
        print(cnt)
        break
    else:
        flag2 = True
        for s in state:
            if not(s in check):

                check.extend(state)
                check = list(set(check))
                flag2 = False
                break
        if flag2 is True:
            flag = False
if flag is False:
    print(-1)