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
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7


def main(): 
    # ダイクストラ法を用いて回答する。
    N, M = LI()
    graph = []
    from collections import defaultdict
    reversed_graph_dict = defaultdict(list)
    for _ in range(M):
        u, v = LI()
        graph.append([u,v])
        reversed_graph_dict[v].append(u)
    S, T = LI()

    # 三段先のグラフを先に作っておく。
    three_steps_dict = defaultdict(list)
    for i in range(1, N+1):
        added = set()
        first_step = reversed_graph_dict[i]
        second_step = []
        for x in first_step:
            second_step += reversed_graph_dict[x]
        third_step = []
        for x in set(second_step):
            for y in reversed_graph_dict[x]:
                if (i,y) not in added:
                    three_steps_dict[i] += [(y, 1)]
                    added.add((i,y))

    N = N+1  # 頂点の数。one-origin の場合は頂点の数+1する。
    S, T = T, S  # 始点、終点の番号

    from heapq import heappop, heappush
    inf=10 ** 18
    d=[inf for i in range(N)]
    d[S]=0  # 始点のコストを 0 とする。頂点は zero origin とする。
    prev=[None]*N

    # 辺のリストを、連結リストに変換する。始点: (終点, 辺のコスト) の list
    p=three_steps_dict

    # ここからダイクストラ法の本体。「重みつき幅優先探索」って感じ。
    q=[(d[S], S)]  # heap queue。中身は (頂点のコスト, 頂点の番号)。始点をまずは格納する。
    while q:
        # print(q,d,prev)
        du, u = heappop(q)  # queue に入っている、コスト最小の頂点を取得する。
                            # この時点で u の最小値は du に確定するので、if u == T: break してもよい。
        if u==T: break
        if d[u]<du: continue  # 点 u のコストがすでに取得したコストよりも少なかったら、更新せずに次へ。
        for v,weight in p.get(u,[]):  # u から伸びる全辺について、
            alt=du+weight
            if d[v]>alt:  # u から v に行ったほうがいまの v のコストよりも低いなら、v のコストを更新して queue へ。
                d[v]=alt
                prev[v]=u  # その点までの最短経路を覚えておく（1つ前の頂点を覚えておく）。
                heappush(q, (alt,v))

    # 終点までの距離を表示する。
    print(d[T] if d[T] != inf else -1)



main()

Submission status: Time Limit Exceeded

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

def kenkenpa(k,n):
    # calculate possible nodes reachable from each node by kenkenpa.
    direction        = n.copy()
    reachable_first  = k.copy()
    # reachable_second = [[] for i in range(len(direction))]
    for ikenpa in range(3):
        reachable_second = [[] for i in range(len(direction))]
        for inode in range(len(reachable_first)):
            # print(inode)
            for ireachable in reachable_first[inode]:
                for idir in direction[ireachable-1]:
                    # print(inode+1,"to",ireachable,"to",idir)
                    if not idir in reachable_second[inode]:
                        reachable_second[inode].append(idir)

        # print(reachable_second)
        reachable_first = reachable_second.copy()

    return reachable_second

# print(n)
for i in range(M):
    U, V = map(int, input().split())
    n[U-1].append(V)
S,T = map(int ,input().split())
# print(n)

notfound = True
k=[[i+1] for i in range(N)]
Nk = 0
while notfound:
    # print(k)
    if T in k[S-1]:
        notfound = False
    else:
        Nk+=1
    k = kenkenpa(k, n)
    if Nk>N:
        Nk=-1
        break
    # notfound=False
# for i in range(M)
print(Nk)

Submission status: Time Limit Exceeded

Solution code:
NM=list(map(int,input().split()))
N=NM[0]
M=NM[1]
graph=[[] for j in range(N)]

for i in range(M):
  edge=list(map(int,input().split()))
  graph[edge[0]-1].append(edge[1]-1)
  
ST=list(map(int,input().split()))
S=ST[0]-1
T=ST[1]-1



first=[]
second=[]
third=[]
able=[S]

step=0

while True:
  first=[]
  second=[]
  third=[]
  judge = 0
  for i in range(len(able)):
    for j in range(len(graph[able[i]])):
      if not (graph[able[i]][j] in first):
        first.append(graph[able[i]][j])
  for i in range(len(first)):
    for j in range(len(graph[first[i]])):
      if not (graph[first[i]][j] in second):
        second.append(graph[first[i]][j])
  for i in range(len(second)):
    for j in range(len(graph[second[i]])):
      if not (graph[second[i]][j] in third):
        third.append(graph[second[i]][j])
  for i in range(len(third)):
      if not third[i] in able:
        able.append(third[i])
        judge = 1
  if judge == 0:
    print(-1)
    break
  step+=1
  if T in able:
    print(step)
    break

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))
graph = defaultdict(list)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].append(v+n)
  graph[u+n].append(v+2*n)
  graph[u+2*n].append(v)
s, t = list(map(int, input().split()))
dist = [-1 for i in range(3*n+10)]

def bfs():
  que = [(s, 0)]
  while len(que) > 0:
    cur, cost = que.pop(0)
    dist[cur] = cost
    for to in graph[cur]:
      if dist[to] == -1:
        que.append((to, cost+1))

bfs()
print(dist[t]//3)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))
graph = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].add(v+n)
  graph[u+n].add(v+2*n)
  graph[u+2*n].add(v)
s, t = list(map(int, input().split()))
dist = [-1 for i in range(3*n+10)]

def bfs():
  que = [(s, 0)]
  while len(que) > 0:
    cur, cost = que.pop(0)
    if dist[cur] != -1:
      continue
    dist[cur] = cost
    for to in graph[cur]:
      que.append((to, cost+1))

bfs()
print(dist[t]//3)

Submission status: Time Limit Exceeded

Solution code:
NM=list(map(int,input().split()))
N=NM[0]
M=NM[1]
graph=[[0 for i in range(N)] for j in range(N)]

for i in range(M):
  edge=list(map(int,input().split()))
  graph[edge[0]-1][edge[1]-1]=1
  
ST=list(map(int,input().split()))
S=ST[0]-1
T=ST[1]-1



first=[]
second=[]
third=[]
able=[S]

step=0

while True:
  first=[]
  second=[]
  third=[]
  judge = 0
  for i in range(len(able)):
    for j in range(N):
      if (graph[able[i]][j] == 1) and not (j in first):
        first.append(j)
  for i in range(len(first)):
    for j in range(N):
      if (graph[first[i]][j] == 1) and not (j in second):
        second.append(j)
  for i in range(len(second)):
    for j in range(N):
      if (graph[second[i]][j] == 1) and not (j in third):
        third.append(j)
  for i in range(len(third)):
      if not third[i] in able:
        able.append(third[i])
        judge = 1
  if judge == 0:
    print(-1)
    break
  step+=1
  if T in able:
    print(step)
    break

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))
graph = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].add(v)
s, t = list(map(int, input().split()))
dist = [[-1 for i in range(3)] for i in range(10**5+10)]

def bfs():
  que = [(s, 0, 0)] #(x, cost, kenkenpa)
  while len(que) > 0:
    p = que.pop(0)
    if dist[p[0]][p[2]] != -1:
      continue
    dist[p[0]][p[2]] = p[1]
    for nx in graph[p[0]]:
      que.append((nx, p[1]+1, (p[2]+1)%3))

bfs()
print(dist[t][0]//3)

Submission status: Time Limit Exceeded

Solution code:
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())

G=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
for _ in range(M):
	u,v = map(int, input().split())
	G[u].append(v)

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

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# グラフGから、3つ先の到達点のグラフXを作る
X=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]

for i in range(N+1):
	g = G[i]

	for g1 in g:
		for g2 in G[g1]:
			for g3 in G[g2]:
#				if (not g3 in X[i]):
#					X[i].append(g3)
				X[i].append(g3)

#p("X",X)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[-1 for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
V[S]=0

# キューに行き先候補を入れて、
from collections import deque

Q = deque()
Q.append(S)

while Q:
	fm = Q.popleft()
#	p("fm, X[fm], Q ", fm, X[fm], Q)
	
	for to in X[fm]:
#		p("  to, V[to], Q ",to, V[to], Q)
		
		b = (V[to]==-1)							# 未訪問である
		#b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to] = V[fm]+1		# 訪問ステップ数の記録
			Q.append(to)			# 次の訪問先として、キューに追加

#	p("V ",V)

#ans = V[T] if V[T]>0 else -1
#print(ans)

print(V[T])

Submission status: Time Limit Exceeded

Solution code:
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())

G=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
for _ in range(M):
	u,v = map(int, input().split())
	G[u].append(v)

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

#p("N,M",N,M)
#p("G",G)
#p("S,T",S,T)


# グラフGから、3つ先の到達点のグラフXを作る
X=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]

for i in range(N+1):
	g = G[i]

	for g1 in g:
		for g2 in G[g1]:
			for g3 in G[g2]:
				if (not g3 in X[i]):
					X[i].append(g3)

#p("X",X)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[-1 for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
V[S]=0

# キューに行き先候補を入れて、
from collections import deque

Q = deque()
Q.append(S)

while Q:
	fm = Q.popleft()
#	p("fm, X[fm], Q ", fm, X[fm], Q)
	
	for to in X[fm]:
#		p("  to, V[to], Q ",to, V[to], Q)
		
		b = (V[to]==-1)							# 未訪問である
		b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to] = V[fm]+1		# 訪問ステップ数の記録
			Q.append(to)			# 次の訪問先として、キューに追加

#	p("V ",V)

#ans = V[T] if V[T]>0 else -1
#print(ans)

print(V[T])

Submission status: Time Limit Exceeded

Solution code:
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
N, M = map(int, input().split())

G=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
for _ in range(M):
	u,v = map(int, input().split())
	G[u].append(v)

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

p("N,M",N,M)
p("G",G)
p("S,T",S,T)


# グラフGから、3つ先の到達点のグラフXを作る
X=[[] for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]

for i in range(N+1):
	g = G[i]

	for g1 in g:
		for g2 in G[g1]:
			for g3 in G[g2]:
				if (not g3 in X[i]):
					X[i].append(g3)

p("X",X)


# 訪問済み＆移動数の記録用マップ、Visitedを作る。未訪問は-1
V=[-1 for _ in range(N+1) ]			#=> [[], [], [], [], [], [], [], []]
V[S]=0

# キューに行き先候補を入れて、
from collections import deque

Q = deque()
Q.append(S)

while Q:
	fm = Q.popleft()
	p("fm, X[fm], Q ", fm, X[fm], Q)
	
	for to in X[fm]:
		p("  to, V[to], Q ",to, V[to], Q)
		
		b = (V[to]==-1)							# 未訪問である
		b = b or (V[to]>(V[fm]+1))	# より短いステップ数である(＝既存の方が大きい)
		if b:
			V[to] = V[fm]+1		# 訪問ステップ数の記録
			Q.append(to)			# 次の訪問先として、キューに追加

	p("V ",V)

ans = V[T] if V[T]>0 else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dfs():
  while len(q) > 0:
    p = q.pop()
    for e in g[p]:
      if d[e] < 0 or d[e] > d[p] + 1:
        d[e] = d[p] + 1
        q.append(e)
  
  
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[3*u].append(3*v+1)
  g[3*u+1].append(3*v+2)
  g[3*u+2].append(3*v)

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

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

q = [3*s]
dfs()
print(d[3*t] // 3)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    tmp=[0]*(n+1)
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if tmp[j]==0 or tmp[j]%3!=ans%3:
                    w.appendleft(j)
                    tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)
 
if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

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

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
#print(a)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    c2 = []
    for u in c:
      m[u][count %3] = True
      for v in a[u]:
        if (v == T and count %3 ==0):
          return count//3
        if not(m[v][(count+1) %3]):
          c2.append(v)
    c = c2
  return -1
print(main())

Submission status: Time Limit Exceeded

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

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

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

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

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

from queue import *
N, M = map(int, input().split())
N *= 3
es = [[] for i in range(N)]
for i in range(M):
    u, v = map(lambda x : (int(x)-1)*3, input().split())
    es[u].append(v+1)
    es[u+1].append((v+2))
    es[u+2].append((v))
S, T = map(lambda x : (int(x)-1)*3, input().split())
dist = [-1 for i in range(N)]
dist[S] = 0
q = Queue()
q.put(S)
while not q.empty():
    v = q.get()
    for u in es[v]:
        if dist[u] == -1:
            dist[u] = dist[v] + 1
            q.put(u)
if dist[T] != -1:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
#print(a)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    vs = []
    for u in c:
      m[u][count %3] = True
      vs += a[u]
    c = []
    for v in vs:
      if (v == T and count %3 ==0):
        return count//3
      if not(m[v][(count+1) %3]):
        c.append(v)
  return -1
print(main())

Submission status: Time Limit Exceeded

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

def next_kenp(node, edges):
    nodes = set()
    nodes2 = set()
    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)
    for n2 in nodes2:
        for n3 in edges[n2]:
            nodes.add(n3)
    return nodes


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

    edges = defaultdict(list)

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

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

    # print(new_edges)

    dones = set()
    que = [((s, 0), 0)]
    while que:
        node, step = que.pop(0)

        next_nodes = edges[node]
        # print(next_nodes)
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def get3(x):
  r1 = a[x]
  r2 = []
  for u in r1:
    r2 += a[u]
  r3 = []
  m = [False] * (N+1)
  for u in r2:
    for v in a[u]:
      if not(m[v]):
        m[v] = True
        r3.append(v)
  return r3
  
S, T = map(int, input().split())
def main():
  c = [S]
  m = [False] * (N+1)
  for count in range(1, N+1):
    vs = []
    for u in c:
      m[u] = True
      vs += get3(u)
    c = []
    for v in vs:
      if (v == T):
        return count
      if not(m[v]):
        c.append(v)
  return -1
print(main())

Submission status: Time Limit Exceeded

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

def get3(x):
  r1 = a[x]
  r2 = []
  for u in r1:
    r2 += a[u]
  r3 = []
  for u in r2:
    r3 += a[u]
  return r3
  
S, T = map(int, input().split())
def main():
  c = [S]
  m = [False] * (N+1)
  for count in range(1, N+1):
    vs = []
    for u in c:
      m[u] = True
      vs += get3(u)
    c = []
    for v in vs:
      if (v == T):
        return count
      if not(m[v]):
        c.append(v)
  return -1
print(main())

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
e=[[] for i in range(3*10**5+10)]

[n,m]=i2()
for i in range(m):
 [u,v]=i2()
 u-=1
 v-=1
 e[3*u].append(3*v+1)
 e[3*u+1].append(3*v+2)
 e[3*u+2].append(3*v)
 
[s,t]=i2()
s-=1
t-=1
d=[-1 for i in range(3*10**5+10)]
def bfs(v):
   d[v]=0
   q=[v]
   while len(q):
    v=q.pop(0)
    for i in e[v]:
      if d[i]<0:
         d[i]=d[v]+1
         q.append(i)
   if d[3*t]>-1:
     return d[3*t]//3
   return d[3*t]  
print(bfs(3*s))

Submission status: Time Limit Exceeded

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

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
def main():
	N, M = map(int, input().split())
	mat = [[] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1].append([N+v-1, 1])
		mat[N+u-1].append([2*N+v-1, 1])
		mat[2*N+u-1].append([v-1, 1])

	S, T = map(int, input().split())
	queue = list(mat[S-1])
	visited = [False]*(3*N)
	visited[S-1] = True
	while queue:
		pos, d = queue[0]
		queue = queue[1:]
		if pos == T-1:
			print(d//3)
			return
		visited[pos] = True
		next_positions = mat[pos]
		for next_pos, next_d in next_positions:
			if visited[next_pos]:
				continue
			queue.append([next_pos, d+next_d])
	print(-1)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
	N, M = map(int, input().split())
	mat = [[] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1].append([N+v-1, 1])
		mat[N+u-1].append([2*N+v-1, 1])
		mat[2*N+u-1].append([v-1, 1])

	S, T = map(int, input().split())
	queue = list(mat[S-1])
	visited = [False]*(3*N)
	visited[S-1] = True
	while queue:
		pos, d = queue.pop(0)
		if pos == T-1:
			print(d//3)
			return
		visited[pos] = True
		next_positions = mat[pos]
		for next_pos, next_d in next_positions:
			if visited[next_pos]:
				continue
			queue.append([next_pos, d+next_d])
	print(-1)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
from collections import defaultdict

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 4 * 10 ** 5
dist = [float("inf")] * cnt


que = [S]
dist[S] = 0

while len(que) != 0:
    q = que.pop()
    for v in graph[q]:
        if dist[v] > dist[q] + 1:
            dist[v] = dist[q] + 1
            que.append(v)
if dist[T] != float("inf"):
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

N, M = map(int,input().split())
hen = [list(map(int,input().split())) for i in range(M)]
S, T = map(int,input().split())
hen2 = []
for i in range(N):
    a = []
    for j in hen:
        if j[0]==i+1:
            a.append(j[1])
    hen2.append(a)

queue = [[S,0]]
check = []
dist = [0]

while True:
    if queue == []:
        print(-1)
        break
    Now = queue.pop(0)
    ndist = dist.pop(0)
    if Now == [T,0]:
        print(int(ndist/3))
        break
    
    check.append(Now)
    for i in hen2[Now[0]-1]:
        if [i,(Now[1]+1)%3] not in check:
            queue.append([i,(Now[1]+1)%3])
            dist.append(ndist+1)

Submission status: Time Limit Exceeded

Solution code:
def main():
	N, M = map(int, input().split())
	INF = 2**30-1
	mat = [[] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1].append([N+v-1, 1])
		mat[N+u-1].append([2*N+v-1, 1])
		mat[2*N+u-1].append([v-1, 1])

	S, T = map(int, input().split())
	queue = list(mat[S-1])
	visited = [False]*(3*N)
	visited[S-1] = True
	while queue:
		pos, d = queue.pop()
		if pos == T-1:
			print(d//3)
			return
		visited[pos] = True
		next_positions = mat[pos]
		for next_pos, next_d in next_positions:
			if visited[next_pos]:
				continue
			queue.append([next_pos, d+next_d])
		queue.sort(key=lambda x: x[1])
	print(-1)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

N, M = map(int,input().split())
hen = [list(map(int,input().split())) for i in range(M)]
S, T = map(int,input().split())
hen2 = []
for i in range(N):
    a = []
    for j in hen:
        if j[0]==i+1:
            a.append(j[1])
    hen2.append(a)

queue = [[S,0]]
check = []
dist = [0]

while True:
    if queue == []:
        print(-1)
        break
    Now = queue.pop(0)
    ndist = dist.pop(0)
    if Now == [T,0]:
        print(int(ndist/3))
        break
    
    check.append(Now)
    for i in hen2[Now[0]-1]:
        if [i,(Now[1]+1)%3] not in check:
            queue.append([i,(Now[1]+1)%3])
            dist.append(ndist+1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

N, M = map(int,input().split())
hen = [list(map(int,input().split())) for i in range(M)]
S, T = map(int,input().split())
hen2 = []
for i in range(N):
    a = []
    for j in hen:
        if j[0]==i+1:
            a.append(j[1])
    hen2.append(a)

queue = [[S,0]]
check = []
dist = [0]

while True:
    if queue == []:
        print(-1)
        break
    Now = queue.pop(0)
    ndist = dist.pop(0)
    if Now == [T,0]:
        print(int(ndist/3))
        break
    
    check.append(Now)
    dist.append
    for i in hen2[Now[0]-1]:
        if [i,(Now[1]+1)%3] not in check:
            queue.append([i,(Now[1]+1)%3])
            dist.append(ndist+1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
from collections import defaultdict

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 4
dist = [float("inf")] * cnt


que = [S]
dist[S] = 0
visited = [False] * cnt
visited[S] = True
while len(que) != 0:
    q = que.pop()
    for v in graph[q]:
        if v == q:
            continue
        if dist[v] > dist[q] + 1:
            dist[v] = dist[q] + 1
            visited[v] = True
            que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
from collections import defaultdict

graph = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v + N)
    graph[u + N].append(v + 2 * N)
    graph[u + 2 * N].append(v)
S, T = map(int, input().split())
S -= 1
T -= 1
cnt = 3 * N + 4
dist = [float("inf")] * cnt


que = [S]
dist[S] = 0
visited = [False] * cnt
visited[S] = True
while len(que) != 0:
    q = que.pop()
    for v in graph[q]:
        if v == q:
            continue
        if dist[v] > dist[q] + 1:
            dist[v] = dist[q] + 1
        visited[v] = True
        que.append(v)
if dist[T] % 3 == 0:
    print(dist[T] // 3)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
	N, M = map(int, input().split())
	INF = 2**30-1
	mat = [[INF for _ in range(3*N)] for _ in range(3*N)]
	for _ in range(M):
		u, v = map(int, input().split())
		mat[u-1][N+v-1] = 1
		mat[N+u-1][2*N+v-1] = 1
		mat[2*N+u-1][v-1] = 1
	for i in range(3*N):
		for j in range(3*N):
			for k in range(3*N):
				mat[j][k] = min(mat[j][k], mat[j][i]+mat[i][k])

	S, T = map(int, input().split())
	if mat[S-1][T-1] == INF:
		print(-1)
	else:
		print(mat[S-1][T-1]//3)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import queue
INF=-1

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

to=[[] for _ in range(N)]

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

dist=[[INF for i in range(3)] for j in range(N)]
q=queue.Queue()
q.put([S,0])
dist[S][0]=0

while(not q.empty()):
    v,l=q.get()
    for v_to in to[v]:
        nl=(l+1)%3
        if dist[v_to][nl] != INF:
            continue
        dist[v_to][nl]=dist[v][l]+1
        q.put([v_to,nl])
ans=dist[T][0]
if ans == INF:
    ans = -1
else:
    ans=ans//3

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

N, M = map(int,input().split())
hen = [list(map(int,input().split())) for i in range(M)]
S, T = map(int,input().split())
hen2 = []
for i in range(N):
    a = []
    for j in hen:
        if j[0]==i+1:
            a.append(j[1])
    hen2.append(a)
    
l0 = []
l1 = []
l2 = []
queue = [[S,0,0]]
check = []

while True:
    if queue == []:
        print(-1)
        break
    Now = queue.pop(0)
    if Now[0]==T and Now[1]==0:
        print(int(Now[2]/3))
        break
    
    check.append(Now)
    for i in hen2[Now[0]-1]:
        judge = 0
        for j in check:
            if j[0] == i and j[1]==(Now[1]+1)%3:
                judge = 1
        if judge == 0:
            queue.append([i,(Now[1]+1)%3,Now[2]+1])