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
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)

N, M = [int(x) for x in input().split()]

# E = {set() for _ in range(N + 1)}
E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = {start}
    w = dict()
    w[start] = 0
    while len(open) != 0:
        target = min(open, key=lambda x: w[x])
        open.remove(target)
        for next in E[target]:
            if not next in w:
                open.add(next)
                w[next] = w[target] + 1

    return w[end] // 3 if end in w else -1


print(bfs(E, S, T))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)

N, M = [int(x) for x in input().split()]

# E = {set() for _ in range(N + 1)}
E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = {start}
    w = defaultdict(lambda: -1)
    w[start] = 0
    while len(open) != 0:
        target = min(open, key=lambda x: w[x])
        open.remove(target)
        for next in E[target]:
            if w[next] == -1:
                open.add(next)
                w[next] = w[target] + 1
    return w[end] // 3


print(bfs(E, S, T))

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    INF = float("inf")
    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] += [v]
    S, T = map(int,input().split())
    S -= 1
    T -= 1
    D = [[INF,INF,INF] for k in range(N)]
    D[S][0] = 0
    Q = [[S,0]]
    while len(Q) > 0:
        ima = Q[0][0]
        k = Q[0][1]
        Q.pop(0)
        for tsugi in G[ima]:
            if D[tsugi][(k+1)%3] != INF:
                pass
            else:
                D[tsugi][(k+1)%3] = D[ima][k] + 1
                Q.append([tsugi,(k+1)%3])
    if D[T][0] == INF or D[T][0]%3 != 0:
        print(-1)
    else:
        print(D[T][0]//3)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def mv(nodes,mvinfo):
    dists=set()
    for node in nodes:
        dists=dists | set(mvinfo[node-1])
    return list(dists)


N,M=[int(e) for e in input().split(' ')]

# 1step
mv1=[[] for n in range(N)]

for i in range(M):
    u,v=[int(e) for e in input().split(' ')]
    mv1[u-1].append(v)
S,T=[int(e) for e in input().split(' ')]

# 1step to 3steps
mv3=[]
for i in range(N):
    mv3.append(mv(mv(mv1[i],mv1),mv1))

# search
reached=set()
for i in range(1,1+N):
    if i==1:
        dists=mv3[S-1]
    else:
        dists=mv(dists,mv3)

    if T in dists:
        break
    
    dists=list(set(dists)-reached)
    reached=reached | set(dists)
else:
    i=-1
print(i)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*
N,M,*E,S,T=map(int,open(0).read().split())
x=csgraph.dijkstra(csr_matrix(([1]*3*M,(sum([[i,i+N,i+2*N]for i in E[::2]],[]),sum([[i+N,i+2*N,i]for i in E[1::2]],[]))),[3*N+1]*2),1,S)[T]
print(x>1e9and-1or int(x//3))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
UV = [list(map(int,input().split())) for _ in range(M)]
s,t = list(map(int,input().split()))

Nei = [[[] for xxx in range(3)] for _ in range(N+1)]

for u,v in UV:
    Nei[u][0].append([v,1])
    Nei[u][1].append([v,2])
    Nei[u][2].append([v,0])
inf = float('inf')
memo = [[inf]*3 for _ in range(N+1)]

def bfs(Q,curr,memo):
    while True:
        for node,step in Nei[curr[0]][curr[1]]:
            if memo[node][step] == inf:
                Q.append([node,step])
                memo[node][step] = memo[curr[0]][curr[1]] + 1
        if len(Q) == 0:
            return memo
        else:
            curr = Q.pop(0)
queue = []
memo[s][0] = 0
Ans = bfs(queue,[s,0],memo)
print(-1 if Ans[t][0] == inf else Ans[t][0]//3)

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 = [ set() for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[v].add(u)
s,t = inm()
s -= 1
t -= 1

reach2 = [ set() for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ set() for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = set()
    for v1 in dst[f]:
        if not m2done[v1]:
            y = set()
            for v2 in dst[v1]:
                for v3 in dst[v2]:
                    y.add(v3)
            reach2[v1] = y
            m2done[v1] = True

        for v3 in reach2[v1]:
                    if v3 == f:
                        continue
                    x.add(v3)
    reach3[f] = x
    m3done[f] = True

dist = [-1] * n
dist[t] = 0
q = deque([(t,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==s:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

input = sys.stdin.readline

N, M = map(int,input().split())
vy = [list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
s, t = map(lambda x:int(x)-1,input().split())

nlist = [[] for i in range(N)]
for v, y in vy:
    nlist[v].append(y)

newnlist = [set() for i in range(N)]
for i in range(N):
    for first in nlist[i]:
        for second in nlist[first]:
            for third in nlist[second]:
                newnlist[i].add(third)

def bfs():
    visit = [False] * N
    Q = queue.Queue()
    visit[s] = True
    Q.put([s,0])
    while not Q.empty():
        node = Q.get()
        if node[0] == t:
            return node[1]
        for i in newnlist[node[0]]:
            if not visit[i]:
                visit[i] = True
                Q.put([i,node[1]+1])
    return -1

ans = bfs()
print(ans)

Submission status: Time Limit Exceeded

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

adjacent_dict={}
for u,v in UV:
  adjacent_dict.setdefault((u,0),set()).add((v,1))
  adjacent_dict.setdefault((u,1),set()).add((v,2))
  adjacent_dict.setdefault((u,2),set()).add((v,0))
  
#BFS
to_visit = set([(S,0)])
visited = set()
n=1

while to_visit:
  #print(to_visit, visited, n)
  _next = set()
  for v in to_visit:
    if v in adjacent_dict:
      for w in adjacent_dict[v]:
        if w not in visited:
          _next.add(w)
  _next = _next - visited
  if (T,0) in _next:
    print(n//3)
    break
  to_visit = _next
  visited = visited | _next
  n += 1
  #print(to_visit, visited, n)
    
else:
  print(-1)

Submission status: Time Limit Exceeded

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

adjacent_dict={}
for u,v in UV:
  adjacent_dict.setdefault((u,0),set()).add((v,1))
  adjacent_dict.setdefault((u,1),set()).add((v,2))
  adjacent_dict.setdefault((u,2),set()).add((v,0))
  
#BFS
to_visit = set([(S,0)])
visited = set()
n=1

while to_visit:
  #print(to_visit, visited, n)
  _next = set()
  for v in to_visit:
    if v in adjacent_dict:
      _next = _next.union(adjacent_dict[v])
  _next = _next - visited
  if (T,0) in _next:
    print(n//3)
    break
  to_visit = _next
  visited = visited | _next
  n += 1
  #print(to_visit, visited, n)
    
else:
  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 = [ set() for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[v].add(u)
s,t = inm()
s -= 1
t -= 1

reach2 = [ set() for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ set() for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = set()
    if not m2done[f]:
        y = set()
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.add(v2)
        reach2[f] = y
        m2done[f] = True

    for v2 in reach2[f]:
                for v3 in dst[v2]:
                    if v3 == f:
                        continue
                    x.add(v3)
    reach3[f] = x
    m3done[f] = True

dist = [-1] * n
dist[t] = 0
q = deque([(t,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==s:
            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 = [ set() for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[v].add(u)
s,t = inm()
s -= 1
t -= 1

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = set()
    if not m2done[f]:
        y = set()
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.add(v2)
        reach2[f] = list(y)
        m2done[f] = True

    for v2 in reach2[f]:
                for v3 in dst[v2]:
                    if v3 == f:
                        continue
                    x.add(v3)
    reach3[f] = list(x)
    m3done[f] = True

dist = [-1] * n
dist[t] = 0
q = deque([(t,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==s:
            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[v].append(u)
s,t = inm()
s -= 1
t -= 1

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = set()
    if not m2done[f]:
        y = set()
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.add(v2)
        reach2[f] = list(y)
        m2done[f] = True

    for v2 in reach2[f]:
                for v3 in dst[v2]:
                    if v3 == f:
                        continue
                    x.add(v3)
    reach3[f] = list(x)
    m3done[f] = True

dist = [-1] * n
dist[t] = 0
q = deque([(t,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==s:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {i+1 : [] for i  in range(n)}
for _ in range(m):
    u, v = map(int, input().split())
    d[u].append(v)
s, t = map(int, input().split())
q = set([s])
visited = set([s])
c = 1
def solve():
    global visited, c, q
    while True:
        q2 = list(q)
        q = set([])
        for v in q2:
            es = set([e3 for e1 in d[v] for e2 in d[e1] for e3 in d[e2]]) - visited
            if t in es:
                return c
            else:
                visited |= es
                q |= es
        if not len(q):
            return -1
        c += 1
print(solve())

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)
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]:
        step1 |= edge[ii]
    step2 = set()
    for iii in step1:
        step2 |= edge[iii]
    step3 = set()
    for iiii in step2:
        kenedge[i].add(iiii)

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

q = Queue()
q.put(s)
reached[s] = True
while not q.empty():
    node = q.get()
    for next_node in kenedge[node]:
        if reached[next_node]: continue
        reached[next_node] = True
        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 defaultdict
from queue import Queue

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

q = Queue()
q.put((s, 0))
while not q.empty():
    node, step = q.get()
    next_step = (step + 1) % 3
    for next_node in edge[node]:
        if reached[next_node][next_step]: continue
        q.put((next_node, next_step))
        reached[next_node][next_step] = True
        if step == 2:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step] + 1)
        else:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step])

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {i+1 : [] for i  in range(n)}
for _ in range(m):
    u, v = map(int, input().split())
    d[u].append(v)
s, t = map(int, input().split())
q = set([s])
visited = set([s])
c = 1
def solve():
    global visited, c, q
    while True:
        for v in list(q):
            q.remove(v)
            es =set([e3 for e1 in d[v] for e2 in d[e1] for e3 in d[e2] if not e3 in visited])
            if t in es:
                return c
            else:
                visited |= es
                q |= es
        if not len(q):
            return -1
        c += 1
print(solve())

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

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = set()
    if not m2done[f]:
        y = set()
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.add(v2)
        reach2[f] = list(y)
        m2done[f] = True

    for v2 in reach2[f]:
                for v3 in dst[v2]:
                    if v3 == f:
                        continue
                    x.add(v3)
    reach3[f] = list(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:
def solve():
    N, M = map(int, input().split())
    G = [[int(i) for i in input().split()] for _ in range(M)]
    S, T = map(int, input().split())
    # 有向グラフをN倍化する
    G_ = double_directed_graph(G, 3)
    # func.ppprint(G_)
    # 幅優先探索
    start_map = [[] for _ in range(N + 1)]
    for g in G_:
        start_map[g[0]].append(g)
    count = 0
    queue = [(S, 0)]
    while True:
        if count >= len(queue):
            # 条件達成経路無し
            break
        tag = queue[count]
        if tag[1] > M:
            # 条件達成経路無し
            break
        if tag[0] == T:
            # 条件達成
            print(tag[1])
            return
        for smg in start_map[tag[0]]:
            queue.append((smg[1], tag[1] + 1))
        count += 1
    print(-1)


def double_directed_graph(edge, n):
    # argument check
    # if n < 2:
    #     raise ValueError('please set n >= 2')
    # main
    import copy
    max_node = 0
    for e in edge:
        max_node = max([max_node] + e)
    start_map = [[] for _ in range(max_node + 1)]
    result = copy.deepcopy(edge)
    for r in result:
        # r.append([[r[0], r[1]]])
        start_map[r[0]].append([r[0], r[1]])
    for i in range(n - 1):
        new_ver = []
        for r in result:
            # 終わりから始まる経路を抜き出す
            tag = start_map[r[1]]
            # tag = [vv for vv in edge if vv[0] == r[1]]
            # 経路の行先分だけ経路を複製する
            for t in tag:
                # print('tag', tag)
                v2 = r.copy()
                v2[1] = t[1]
                # v2[2].append(t.copy())
                new_ver.append(v2)
        result = new_ver
    return result


if __name__ == '__main__':
    solve()

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

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = []
    if not m2done[f]:
        y = []
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.append(v2)
        reach2[f] = list(set(y))
        m2done[f] = True

    for v2 in reach2[f]:
                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:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()

from collections import defaultdict
edges = defaultdict(set)
for i in range(M):
    u, v = nl()
    edges[u].add(v+N)
    edges[u+N].add(v+2*N)
    edges[u+2*N].add(v)

S, T = nl()

import queue
q = queue.Queue()
q.put((S, 0))

done = defaultdict(bool)
done[S] = True

while not q.empty():
    src, cost = q.get()
    for dst in edges[src]:
        if dst == T:
            print((cost+1) // 3)
            import sys
            sys.exit()

        if not done[dst]:
            done[dst] = True
            q.put((dst, cost+1))

print(-1)

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, MX, MX] for i in range(n)]
reached = [[False, False, 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] = 0

q = Queue()
q.put((s, 0))
while not q.empty():
    node, step = q.get()
    next_step = (step + 1) % 3
    reached[node][step] = True
    for next_node in edge[node]:
        if reached[next_node][next_step]: continue
        q.put((next_node, next_step))
        if step == 2:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step] + 1)
        else:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step])

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

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, MX, MX] for i in range(n)]
reached = [[False, False, 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] = 0

q = Queue()
q.put((s, 0))
while not q.empty():
    node, step = q.get()
    next_step = (step + 1) % 3
    reached[node][step] = True
    for next_node in edge[node]:
        if not reached[next_node][next_step]: q.put((next_node, next_step))
        if step == 2:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step] + 1)
        else:
            dist[next_node][next_step] = min(dist[next_node][next_step], dist[node][step])

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

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

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = []
    if not m2done[f]:
        y = []
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.append(v2)
        reach2[f] = y
        m2done[f] = True

    for v2 in reach2[f]:
                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)])
nodedone = [False for i in range(n)]
while len(q)>0:
    v,d = q.popleft()
    if not m3done[v]:
        mark(v)
    for nxt in reach3[v]:
        if dist[nxt] > -1 or nodedone[nxt]:
            continue
        nodedone[nxt] = True
        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
sys.setrecursionlimit(200000)
def main():
    INF = float("inf")
    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 = [[INF,INF,INF] for k in range(N)]
    D1[S][0] = 0

    def dfs1(now):
        for tsugi in G[now][1]:
            if D1[tsugi][1] > D1[now][0] + 1:
                D1[tsugi][1] = D1[now][0] + 1
                dfs2(tsugi)
    def dfs2(now):
        for tsugi in G[now][2]:
            if D1[tsugi][2] > D1[now][1] + 1:
                D1[tsugi][2] = D1[now][1] + 1
                dfs3(tsugi)
    def dfs3(now):
        for tsugi in G[now][2]:
            if D1[tsugi][0] > D1[now][2] + 1:
                D1[tsugi][0] = D1[now][2] + 1
                dfs1(tsugi)

    dfs1(S)
    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())

to = [[] for _ in range(N)]
dist = [[0 for _ in range(3)] for _ in range(100005)]
for i in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  to[a].append(b)

sv, tv = map(int, input().split())
sv -= 1
tv -= 1

for i in range(N):
  for j in range(3):
    dist[i][j] = float("inf")
q = [[sv, 0]]
dist[sv][0] = 0
while len(q) != 0:
  v = q[0][0]
  l = q[0][1]
  q.pop(0)
  for u in to[v]:
    nl = (l + 1) % 3
    if dist[u][nl] != float("inf"):
      continue
    dist[u][nl] = dist[v][l] + 1
    q.append([u, nl])
ans = dist[tv][0]
if ans == float("inf"):
  ans = -1
else:
  ans //= 3
print(ans)

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

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = []
    if not m2done[f]:
        y = []
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.append(v2)
        reach2[f] = y
        m2done[f] = True

    for v2 in reach2[f]:
                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:
from collections import deque
from itertools import chain


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)


def find_next(pos, e):
    c1 = e[pos]
    c2 = list(chain.from_iterable([e[c]for c in c1]))
    return list(chain.from_iterable([e[c] for c in c2]))


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

visited = set()
cost = 0
st = deque([(s, 0)])
ans = -1
pre = None
while len(st):
    pos, cost = st.popleft()
    if pos == t:
        ans = cost
        break
    for n in find_next(pos, edges):
        if not (pos, n) in visited:
            st.append((n, cost + 1))
            visited.add((pos, n))

print(ans)