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 deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
s,t = map(int,input().split())
visited = [[-1,-1,-1] for i in range(n+1)]
que = deque([(s,0,0)])
while que:
  x,mod,cnt = que.popleft()
  visited[x][mod] = cnt
  if x == t and mod == 0:
    break
  for y in graph[x]:
    if visited[y][(mod+1)%3] == -1:
      que.append((y,(mod+1)%3,cnt+1))
      visited[y][(mod+1)%3] == cnt+1
print(visited[t][0]//3)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
s,t = map(int,input().split())
visited = [[-1,-1,-1] for i in range(n+1)]
que = deque([(s,0,0)])
while que:
  x,mod,cnt = que.popleft()
  visited[x][mod] = cnt
  if x == t and mod == 0:
    break
  for y in graph[x]:
    if visited[y][(mod+1)%3] == -1:
      que.append((y,(mod+1)%3,cnt+1))
print(visited[t][0]//3)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INFTY = 10**6
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    u,v = map(int,input().split())
    G[u].append(v)
dist = [[[] for i in range(N+1)] for k in range(4)]
for i in range(1,N+1):
    dist[1][i] = G[i]
for i in range(1,N+1):
    dist[2][i] = []
    for j in dist[1][i]:
        dist[2][i] += dist[1][j]
for i in range(1,N+1):
    dist[3][i] = []
    for j in dist[2][i]:
        dist[3][i] += dist[1][j]
S,T = map(int,input().split())
que = deque([[S,0]])
d = [INFTY for _ in range(N+1)]
d[S] = 0
hist = [0 for _ in range(N+1)]
hist[S] = 1
while que:
    x,c = que.popleft()
    for y in dist[3][x]:
        if hist[y]==0:
            que.append([y,c+1])
            d[y] = c+1
            hist[y]=1
if d[T]==INFTY:
    print(-1)
else:
    print(d[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INFTY = 10**6
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    u,v = map(int,input().split())
    G[u].append(v)
dist = [[[] for i in range(N+1)] for k in range(4)]
for i in range(1,N+1):
    dist[1][i] = G[i]
for i in range(1,N+1):
    dist[2][i] = []
    for j in dist[1][i]:
        dist[2][i] += dist[1][j]
    dist[2][i] = list(set(dist[2][i]))
for i in range(1,N+1):
    dist[3][i] = []
    for j in dist[2][i]:
        dist[3][i] += dist[1][j]
    dist[3][i] = list(set(dist[3][i]))
S,T = map(int,input().split())
que = deque([[S,0]])
d = [INFTY for _ in range(N+1)]
d[S] = 0
hist = [0 for _ in range(N+1)]
hist[S] = 1
while que:
    x,c = que.popleft()
    for y in dist[3][x]:
        if hist[y]==0:
            que.append([y,c+1])
            d[y] = c+1
            hist[y]=1
if d[T]==INFTY:
    print(-1)
else:
    print(d[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def dist(i,k):
    if k==3:
        for j in G[i]:
            a.append(j)
    else:
        for j in G[i]:
            dist(j,k+1)
    
INFTY = 10**6
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    u,v = map(int,input().split())
    G[u].append(v)
A = {}
for i in range(1,N+1):
    a = []
    dist(i,1)
    A[i] = a
S,T = map(int,input().split())
que = deque([[S,0]])
d = [INFTY for _ in range(N+1)]
d[S] = 0
hist = [0 for _ in range(N+1)]
hist[S] = 1
while que:
    x,c = que.popleft()
    for y in A[x]:
        if hist[y]==0:
            que.append([y,c+1])
            d[y] = c+1
            hist[y]=1
if d[T]==INFTY:
    print(-1)
else:
    print(d[T])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

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

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = [S]
ans[S][0] = 0
while q:
    now = q.pop()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

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

inf = 10**10
ans = [[inf, inf, inf] for i in range(N+1)]

q = [S]
ans[S][0] = 0
while q:
    now = q.pop()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)

Submission status: Time Limit Exceeded

Solution code:
import collections
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = [tuple(map(int, input().split())) for _ in range(M)]
        S, T = map(int, input().split())

        edge_map = collections.defaultdict(list)
        for u, v in edges:
            edge_map[u - 1].append(v - 1)

        q = queue.Queue()
        q.put((S - 1, 0))

        INF = 10 ** 5
        dist = [[INF] * 3 for _ in range(N)]
        dist[S - 1][0] = 0
        while not q.empty():
            node, kkp = q.get()

            for next_node in edge_map[node]:
                next_kkp = (kkp + 1) % 3
                if dist[next_node][next_kkp] == INF:
                    dist[next_node][next_kkp] = dist[node][kkp] + 1
                    q.put((next_node, next_kkp))

        if dist[T - 1][0] == INF:
            print(-1)
        else:
            print(dist[T - 1][0] // 3)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
import collections
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = [tuple(map(int, input().split())) for _ in range(M)]
        S, T = map(int, input().split())

        edge_map = collections.defaultdict(list)
        for u, v in edges:
            edge_map[u].append(v)

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

        dist = collections.defaultdict(lambda: [10 ** 5] * 3)
        dist[S][0] = 0
        while not q.empty():
            node, total_path_length = q.get()

            for next_node in edge_map[node]:
                nl = (total_path_length + 1) % 3
                if dist[next_node][nl] == 10 ** 5:
                    dist[next_node][nl] = total_path_length + 1
                    q.put((next_node, total_path_length + 1))

        if dist[T][0] == 10 ** 5:
            print(-1)
        else:
            print(dist[T][0]//3)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

Solution code:
import collections
import queue
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        edges = [tuple(map(int, input().split())) for _ in range(M)]
        S, T = map(int, input().split())

        edge_map = collections.defaultdict(list)
        for u, v in edges:
            edge_map[u].append(v)

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

        dp = collections.defaultdict(lambda: 10 ** 5)
        ans = 10 ** 5
        while not q.empty():
            node, kkp, cnt = q.get()

            kkp += 1

            if kkp < 3:
                for next_node in edge_map[node]:
                    q.put((next_node, kkp, cnt))
            else:
                for next_node in edge_map[node]:
                    if next_node == T:
                        ans = min(ans, cnt)
                        q = queue.Queue()
                        break
                    elif dp[next_node] > cnt + 1:
                        dp[next_node] = cnt + 1
                        q.put((next_node, 0, cnt + 1))

        if ans == 10 ** 5:
            print(-1)
        else:
            print(ans)

# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Time Limit Exceeded

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

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


for i in range(N):
    for j in range(len(adj[i])):
        a=adj[i][j]
        for k in range(len(adj[a])):
            adj_2[i].append(adj[a][k])
    adj_2[i]=list(set(adj_2[i]))#重複データを外す

    
for i in range(N):
    for j in range(len(adj_2[i])):
        a=adj_2[i][j]
        for k in range(len(adj[a])):
            adj_3[i].append(adj[a][k])
    adj_3[i]=list(set(adj_3[i]))#重複データを外す
    
##########################################
inf=10**9
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """
    
    #最短のpathをたす
    
    
    class Edge():
        #重み付き有向辺
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s):
        #始点sから頂点iまでの最短経路長のリストを返す
        
        que = [] #priority queue
        d = [inf] * self.V()
        prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
        d[s] = 0
        heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
        
        while len(que)!=0:
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
            if d[v] < cost:
                continue
                
            #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost #更新
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

        return d
########################
    

djk = Dijkstra(N)
for i in range(N):
    for j in range(len(adj_3[i])):
        djk.add(i,adj_3[i][j],1)



d = djk.shortest_path(S-1)
ans=d[T-1]
if ans==inf:
    ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

is_visited = [False]*N
is_visited[s] = True

d = deque([s])
ans = 0
while d:
  ans += 1
  diff = 0
  for step in range(1, 4):
    if d:
      len_d = len(d)
      for i in range(len_d):
        node = d.popleft()
        children = graph[node]
        for child in children:
          if step == 3:
            if child == t:
              d = []
              diff = 1
              break
            if not is_visited[child]:
              is_visited[child] = True
              diff += 1
              d.append(child)
          else:
            d.append(child)
        
        else:
          continue
        break
    
    else:
      ans = -1
      break
  
  if not diff:
    ans = -1
    break

print(ans)

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 = map(int, input().split())

before_dict = {}
after_dict = {}
after_3 = {}

for i in range(1,n+1):
    before_dict[i] =[]
    after_dict[i] = []
    after_3[i] = []

for i in range(m):
    u, v = uv[i]
    before_dict[v].append(u)
    after_dict[u].append(v)

for i in range(m):
    u, v = uv[i]
    for j in before_dict[u]:
        for k in after_dict[v]:
            if( j != k):
                after_3[j].append(k)

que = []
que_l = 0

def q_app(num):
    global que
    que.append(num)

def q_pop():
    global que_l
    global que
    que_l += 1
    return que[que_l-1]

q_app(s)

length = [-1] * (n+1)
length[s] = 0

check = True

while(check):
    if((len(que) - que_l) == 0):
        break
    num = q_pop()

    for i in after_3[num]:
        if(length[i] == -1):
            length[i] = length[num] + 1
            q_app(i)

    if(length[t] > -1):
        break

print(length[t])

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 = map(int, input().split())

before_dict = {}
after_dict = {}
after_3 = {}

for i in range(1,n+1):
    before_dict[i] =[]
    after_dict[i] = []
    after_3[i] = []

for i in range(m):
    u, v = uv[i]
    before_dict[v].append(u)
    after_dict[u].append(v)

for i in range(m):
    u, v = uv[i]
    for j in before_dict[u]:
        for k in after_dict[v]:
            if( j != k):
                after_3[j].append(k)

from collections import deque
d = deque()
d.append(s)

length = [-1] * (n+1)
length[s] = 0

check = True

while(check):
    if(len(d) == 0):
        break
    num = d.popleft()
    for i in after_3[num]:
        if(length[i] == -1):
            length[i] = length[num] + 1
            d.append(i)

    if(length[t] > -1):
        break

print(length[t])

Submission status: Time Limit Exceeded

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

stack=[]
INF=10**5*3
seen=[[INF for i in range(3)] for j in range(N)]
stack.append([S,0,1])
ans=INF
while stack:
  node=stack.pop()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      if ans>turn:
        ans=turn
      continue
    step=0
    turn+=1
  if seen[v][step]<=turn:
    continue
  seen[v][step]=turn
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  if ans==INF:
    print(-1)
  else:
    print(ans)

Submission status: Time Limit Exceeded

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

stack=[]
INF=10**9
seen=[[INF for i in range(3)] for j in range(N)]
stack.append([S,0,1])
ans=INF
while stack:
  node=stack.pop()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      if ans>turn:
        ans=turn
      continue
    step=0
    turn+=1
  if seen[v][step]<=turn:
    continue
  seen[v][step]=turn
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  if ans==INF:
    print(-1)
  else:
    print(ans)

Submission status: Time Limit Exceeded

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

def bfs(graph,N,s,t):
    start=time.time()
    S=[s]
    visited=set()
    distance={(i+1,j):0 for i in range(N) for j in range(3)}
    while len(S)>0:
        if time.time()-start==1.7:
            return False,-1
        v=S.pop(0)
        if v==t:
            return True,distance[v]+1
        if v not in visited:
            visited.add(v)
            for w in graph[v]:
                distance[w] = distance[v]+1
                S.append(w)
    return False,-1
if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    flag,ans=bfs(graph,N,(S,0),(T,0))

    if flag:
        print(ans//3)
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

def bfs(graph,N,s,t):
    start=time.time()
    S=[s]
    visited=set()
    distance={(i+1,j):0 for i in range(N) for j in range(3)}
    while len(S)>0:
        if time.time()-start==1.9:
            return False,-1
        v=S.pop(0)
        if v==t:
            return True,distance[v]+1
        if v not in visited:
            visited.add(v)
            for w in graph[v]:
                distance[w] = distance[v]+1
                S.append(w)
    return False,-1
if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    flag,ans=bfs(graph,N,(S,0),(T,0))

    if flag:
        print(ans//3)
    else:
        print(-1)

Submission status: Time Limit Exceeded

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

def bfs(graph,N,s,t):
    S=[s]
    visited=set()
    distance={(i+1,j):0 for i in range(N) for j in range(3)}
    while len(S)>0:
        v=S.pop(0)
        if v==t:
            return True,distance[v]+1
        if v not in visited:
            visited.add(v)
            for w in graph[v]:
                distance[w] = distance[v]+1
                S.append(w)
    return False,-1
if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    E=[list(map(int,input().split())) for _ in range(M)]
    S,T=list(map(int,input().split()))
    graph={(i+1,j):[] for i in range(N) for j in range(3)}
    for e in E:
        graph[(e[0],0)].append((e[1],1))
        graph[(e[0],1)].append((e[1],2))
        graph[(e[0],2)].append((e[1],0))
    flag,ans=bfs(graph,N,(S,0),(T,0))

    if flag:
        print(ans//3)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M=map(int,input().split())
a=[set() for i in range(N)] # 0-index
for i in range(M):
    u,v=map(lambda x:int(x)-1,input().split())
    a[u].add(v)
S,T=map(lambda x:int(x)-1,input().split())
# print(a)
t=[]
for i in range(N):    
    ti=set()
    for u in a[i]:
        for v in a[u]:
            for w in a[v]:
                ti|={w}    
    t.append(ti)
# print(t)
r=[-1 for i in range(N)]
q=deque()
q.append(S);r[S]=0
while q:
    u=q.popleft()
    for v in t[u]:
        if r[v]==-1:
            r[v]=r[u]+1
            q.append(v)
# print(r)
print(r[T])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
G = {k: [] for k in range(N+1)}
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())


visited = [[10**9] * (N+1) for _ in range(3)]


que = deque([(S, 0)])

while que:
    ci, t = que.popleft()
    visited[t % 3][ci] = t

    for ni in G[ci]:
        if visited[(t+1) % 3][ni] > t+1:
            que.append((ni, t+1))

if visited[0][T] == 10**9:
    print(-1)
else:
    print(visited[0][T]//3)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
G = {k: [] for k in range(N+1)}
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())


visited = [[10**9] * (N+1) for _ in range(3)]


que = deque([(S, 0)])

while que:
    ci, t = que.popleft()
    visited[t % 3][ci] = t

    for ni in G[ci]:
        if visited[(t+1) % 3][ni] > t:
            que.append((ni, t+1))

if visited[0][T] == 10**9:
    print(-1)
else:
    print(visited[0][T]//3)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
G = {k: [] for k in range(N+1)}
for _ in range(M):
    u, v = map(int, input().split())
    G[u].append(v)
S, T = map(int, input().split())

visited = [[10**9] * (N+1) for _ in range(4)]


que = deque([(S, 0, 0)])

ans = -1
c = 0
while que:
    ci, t, c = que.popleft()
    if t != 0:
        visited[t][ci] = c
    if t == 3:
        t = 0
        if ci == T:
            ans = c//3
            break

    for ni in G[ci]:
        if visited[t+1][ni] > c:
            que.append((ni, t+1, c+1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

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

edges = [[] for _ in range(N * 3)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to + N)
    edges[fr + N].append(to + 2 * N)
    edges[fr + 2 * N].append(to)

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

minDist = [INF] * (3 * N)
que = [(S, 0)]

while que:
    now, dist = heappop(que)

    if minDist[now] <= dist:
        continue
    minDist[now] = dist

    dist += 1

    for to in edges[now]:
        if minDist[to] > dist:
            heappush(que, (to, dist))

ans = minDist[T]

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import deque

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

dic = {}

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []

    dic[u].append(v)


far = [[float("inf")] * 3 for i in range(N)]
nend = [ [True] * 3 for i in range(N) ]

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

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

while len(q) > 0:

    now = q.popleft()

    nd = now[0]
    np = now[1]
    nend[np][nd % 3] = False

    far[np][nd % 3] = min(far[np][nd % 3],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i][(nd + 1) % 3] and far[i][(nd+1)%3] > far[np][nd%3] + 1:
                q.append([nd + 1 , i])

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

dic = {}

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []

    dic[u].append(v)


far = [[float("inf")] * 3 for i in range(N)]
nend = [ [True] * 3 for i in range(N) ]

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

q = []
heapq.heappush(q,[0,S])

while len(q) > 0:

    now = heapq.heappop(q)

    nd = now[0]
    np = now[1]
    nend[np][nd % 3] = False

    far[np][nd % 3] = min(far[np][nd % 3],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i][(nd + 1) % 3] and far[i][(nd+1)%3] > far[np][nd%3] + 1:
                heapq.heappush(q,[nd + 1 , i])

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

dic = {}

for i in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    if u not in dic:
        dic[u] = []

    dic[u].append(v)


far = [[float("inf")] * 3 for i in range(N)]
nend = [ [True] * 3 for i in range(N) ]

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

q = []
heapq.heappush(q,[0,S])

while len(q) > 0:

    now = heapq.heappop(q)

    nd = now[0]
    np = now[1]
    nend[np][nd % 3] = False

    far[np][nd % 3] = min(far[np][nd % 3],nd)

    if np in dic:
        for i in dic[np]:

            if nend[i][(nd + 1) % 3]:
                heapq.heappush(q,[nd + 1 , i])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1
 
que = deque([(0, s)])
already = set()
flg = False
while que:
    cost, cur = que.popleft()
    already.add(cur)
    if cur == t:
        flg = True
        break
    for i in graph[cur]:
        if i not in already:
            que.append((cost + 1, i))
if not flg:
    cost = -1
else:
    cost //= 3
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [(0, s)]
flg = False
parent = [-1 for i in range(3 * n)]
while que:
    cost, cur = que[0]
    que.pop(0)
    if cur == t:
        flg = True
        break
    for i in graph[cur]:
        if parent[cur] != i:
            que.append((cost + 1, i))
            parent[i] = cur
if not flg:
    cost = -1
else:
    cost //= 3

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = deque([(0, s)])
already = set()
flg = False
while que:
    cost, cur = que.popleft()
    already.add(cur)
    if cur == t:
        flg = True
        break
    for i in graph[cur]:
        if i not in already:
            que.append((cost + 1, i))
if not flg:
    cost = -1
else:
    cost //= 3

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [(0,s)]
already = set()
flg = False
while que:
    cost, cur = heapq.heappop(que)
    already.add(cur)
    if cur == t:
        flg = True
        break
    for i in graph[cur]:
        if i in already:
            continue
        heapq.heappush(que, (cost + 1, i))
if not flg:
    cost = -1
else:
    cost //= 3

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(3 * n)] for j in range(3 * n)]
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u][n+v] = 1
    graph[u+n][2*n+v] = 1
    graph[u + 2 * n][v] = 1
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [(0,s)]
already = set()
flg = False
while que:
    cost, cur = heapq.heappop(que)
    already.add(cur)
    if cur == t:
        flg = True
        break
    for i, _next in enumerate(graph[cur]):
        if _next == 0:
            continue
        if i in already:
            continue
        heapq.heappush(que, (cost + 1, i))
if not flg:
    cost = -1
else:
    cost //= 3

print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(3 * n)] for j in range(3 * n)]
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u][n+v] = 1
    graph[u+n][2*n+v] = 1
    graph[u + 2 * n][v] = 1
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

def dijkstra(graph, s, g):
    que = [(0,s)]
    already = set()
    flg = False
    while que:
        cost, cur = heapq.heappop(que)
        already.add(cur)
        if cur == g:
            flg = True
            break
        for i, _next in enumerate(graph[cur]):
            if _next == 0:
                continue
            if i in already:
                continue
            heapq.heappush(que, (cost + 1, i))
    if not flg:
        cost = -1
        return cost
    return cost // 3

res = dijkstra(graph, s, t)
print(res)