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:
n, m = map(int, input().split(" "))
path = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split(" "))
    path[u-1].append(v)

s, g = map(int, input().split(" "))

def indicate3(start,path):
    for _ in range(3):
        next = []
        for position in start:
            for next_position in path[position-1]:
                next.append(next_position)
        start = next
    return start

stack = [s]
count = 0
while True:
    n_stack = indicate3(stack,path)
    if g in n_stack:
        count += 1
        print(count)
        break
    else:
        if n_stack == stack:
            print(-1)
            break
        else:
            count += 1
    stack = n_stack

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  n,m = (int(i) for i in input().split())
  step = [[] for _ in range(n)] 
  for i in range(m):
    u,v = (int(i) for i in input().split())
    if not v in step[u-1]:
     step[u-1].append(v)

  depth = [len(step[i]) for i in range(n)]
  S,T = (int(i) for i in input().split())
  query = deque([])
  query.append((S,0))
  visit = [False for _ in range(n+2)]
  ans = 5000000
  checker = 0

  while query:

    place,move = query.popleft()
    move += 1 
    if move%3 ==0 and visit[place]:
      continue  
    else:
      if move%3 == 0: 
        visit[place] = True
      for i in range(depth[place-1]):
        query.append((step[place-1][i],move))
        
    if place == T and (move-1)%3 == 0:
      ans = min(ans,move-1)
      break

  if not ans == 5000000:
   print(ans//3)
  else:
    print(-1)
solve()

Submission status: Time Limit Exceeded

Solution code:
def f(n, m):
    to1 = {}
    for _ in range(m):
        u, v = map(int, input().split())
        to1.setdefault(u, [])
        to1[u] += [v]
    s, t = map(int, input().split())

    vst1 = set()
    cnt = 0
    to = {}

    for i in range(1, n + 1):
        ss = set([i])
        for _ in range(3):
            nss = []
            for ii in ss:
                if ii not in to1: continue
                nss+=to1[ii]
            ss = set(nss)
        to[i] = list(ss)

#    print(to)

    ss = set([s])
    while 1:
        cnt += 1
#        print(ss)
        nss=set()
        for i in ss:
            if i not in to: continue
            for j in to[i]:
                nss.add(j)
        ss = nss
#        print(ss)
        if t in ss:
            print(cnt)
            exit()
        if ss <= vst1:
            print(-1)
            exit()
        vst1 |= ss

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

Submission status: Time Limit Exceeded

Solution code:
def f(n, m):
    to1 = {}
    for _ in range(m):
        u, v = map(int, input().split())
        to1.setdefault(u, [])
        to1[u] += [v]
    s, t = map(int, input().split())

    vst1 = set()
    cnt = 0
    to = {}

    for i in range(1, n + 1):
        ss = set([i])
        for _ in range(3):
            nss = set()
            for ii in ss:
                if ii not in to1: continue
                for j in to1[ii]:
                    nss.add(j)
            ss = nss
        to[i] = list(ss)

#    print(to)

    ss = set([s])
    while 1:
        cnt += 1
#        print(ss)
        nss=set()
        for i in ss:
            if i not in to: continue
            for j in to[i]:
                nss.add(j)
        ss = nss
#        print(ss)
        if t in ss:
            print(cnt)
            exit()
        if ss <= vst1:
            print(-1)
            exit()
        vst1 |= ss

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  n,m = (int(i) for i in input().split())
  step = [[] for _ in range(n)] 
  for i in range(m):
    u,v = (int(i) for i in input().split())
    if not v in step[u-1]:
     step[u-1].append(v)


  S,T = (int(i) for i in input().split())
  query = deque([])
  query.append((S,0))
  visit = [False for _ in range(n+2)]
  ans = 5000000
  checker = 0

  while query:

    place,move = query.popleft()
    move += 1 
    if move%3 ==0 and visit[place]:
      continue  
    else:
      if move%3 == 0: 
        visit[place] = True
      for i in range(len(step[place-1])):
        query.append((step[place-1][i],move))
        
    if place == T and (move-1)%3 == 0:
      ans = min(ans,move-1)
      break

  if not ans == 5000000:
   print(ans//3)
  else:
    print(-1)
solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def solve():
  n,m = (int(i) for i in input().split())
  step = [[] for _ in range(n)] 
  for i in range(m):
    u,v = (int(i) for i in input().split())
    if not v in step[u-1]:
     step[u-1].append(v)


  S,T = (int(i) for i in input().split())
  query = deque([])
  query.append((S,0))
  visit = [False for _ in range(n+2)]
  ans = 5000000
  checker = 0
  while (query):
    place,move = query.popleft()
    move += 1 
    if move%3 ==0 and visit[place]:
      continue  
    else:
      if move%3 == 0: 
        visit[place] = True
      for i in range(len(step[place-1])):
        query.append((step[place-1][i],move))
        
    if place == T and (move-1)%3 == 0:
      ans = min(ans,move-1)
      break
    
  if not ans == 5000000:
   print(ans//3)
  else:
    print(-1)
solve()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
uv = [[] for _ in range(n)]
for i in range(m):
  u,v = map(lambda x:int(x)-1,input().split())
  uv[u].append(v)
s,t = map(lambda x:int(x)-1,input().split())
time = 0
now = {s}
flag = 0
for _ in range(n):
  time += 1
  tmp = set()
  for x in now:
    for y in uv[x]:
      tmp.add(y)
  now = tmp
  time += 1
  tmp = set()
  for x in now:
    for y in uv[x]:
      tmp.add(y)
  now = tmp
  time += 1
  tmp = set()
  for x in now:
    for y in uv[x]:
      tmp.add(y)
  now = tmp
  if t in now:
    flag = 1
    break
if flag == 1:
  print(time//3)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
uv = [[] for _ in range(n)]
for i in range(m):
  u,v = map(lambda x:int(x)-1,input().split())
  uv[u].append(v)
s,t = map(lambda x:int(x)-1,input().split())
time = 0
now = {s}
flag = 0
while time < 3*n:
  time += 1
  tmp = set()
  for x in now:
    for y in uv[x]:
      tmp.add(y)
  now = tmp
  if time % 3 == 0:
    if t in now:
      flag = 1
      break
if flag == 1:
  print(time//3)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
uv = [[] for _ in range(n)]
for i in range(m):
  u,v = map(lambda x:int(x)-1,input().split())
  uv[u].append(v)
s,t = map(lambda x:int(x)-1,input().split())
time = 0
now = [s]
flag = 0
while time < 3*n:
  time += 1
  tmp = []
  for x in now:
    for y in uv[x]:
      tmp.append(y)
  now = tmp
  if time % 3 == 0:
    if t in now:
      flag = 1
      break
if flag == 1:
  print(time//3)
else:
  print(-1)

Submission status: Time Limit Exceeded

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

def f(D, S, T):
    close = [[False] * N, [False] * N, [False] * N]
    Q = []
    index = 0
    Q.append((S, 0, 0))

    while len(Q) > index:
        p, c, l = Q[index]
        index += 1
        if l == 0 and p == T:
            return c
        close[l][p] = True

        l, c = (l + 1) % 3, c + (l + 1) // 3
        for n in D[p]:
            if close[l][n]:
                continue
            Q.append((n, c, l))
    return -1

if __name__ == "__main__":
    D = {n: set() for n in range(N)}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D[u].add(v)

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

    print(f(D, S, T))

Submission status: Time Limit Exceeded

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

def f(D, S, T, W):
    close = [set(), set(), set()]
    Q = []
    index = 0
    end = 1
    Q.append((S, 0, 0))

    while end > index:
        p, c, l = Q[index]
        index += 1
        if l == 0 and p == T:
            return c
        close[l].add(p)

        ns = D.setdefault(p, set())
        l, c = (l + 1) % 3, c + (l + 1) // 3
        for n in ns:
            if n in close[l]:
                continue
            Q.append((n, c, l))
            end += 1
    return -1

if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    D = {}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D.setdefault(u, set()).add(v)

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

    print(f(D, S, T, N * M * 10))

Submission status: Time Limit Exceeded

Solution code:
def f(D, S, T, W):
    close = [set(), set(), set()]
    Q = []
    index = 0
    end = 1
    Q.append((S, 0, 0))

    while end > index:
        p, c, l = Q[index]
        index += 1
        if l == 0 and p == T:
            return c
        close[l].add(p)

        ns = D.setdefault(p, set())
        l, c = (l + 1) % 3, c + (l + 1) // 3
        for n in ns:
            if n in close[l]:
                continue
            Q.append((n, c, l))
            end += 1
    return -1

if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    D = {}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D.setdefault(u, set()).add(v)

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

    print(f(D, S, T, N * M * 10))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
L1 = [set() for k in range(N+1)]
for k in range(M):
	u, v = map(int, input().split())
	L1[u].add(v)
S, T = map(int, input().split())
L2 = [None for k in range(N+1)]
L3 = [None for k in range(N+1)]
for n in range(N+1):
	a = set()
	for l in L1[n]:
		a = a.union(L1[l])
	L2[n] = a
	a = set()
	for l in L2[n]:
		a = a.union(L1[l])
	a.discard(n)
	L3[n] = a
t = 0
sumi = set([S])
now = set([S])
flg = 0
ansT = set([T])
while(len(now) != 0):
	t +=1
	pre = set()
	for d in now:
		pre = pre.union(L3[d])
	now = pre - sumi
	sumi = sumi.union(now)
	if ansT <= sumi:
		print(t)
		flg = 1
		now = set()
if flg == 0:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v)
S, T = map(int, input().split())
S, T = S-1, T-1
new1 = [[] for i in range(N)]
new2 = [[] for i in range(N)]
new3 = [[] for i in range(N)]
for i in range(N):
    for v in graph[i]:
        new1[i].append(v)
for i in range(N):
    for v in graph[i]:
        new2[i].extend(new1[v])
for i in range(N):
    for v in graph[i]:
        new3[i].extend(new2[v])
#print(new1)
#print(new2)
#print(new3)



visit = [False for i in range(N)]
length = [0 for i in range(N)]
def bfs(v, T):
    Q = []
    Q.append(v)
    visit[v] = True
    while len(Q) > 0:
        v = Q.pop(0)
        #print(con)
        con = list(set(new3[v]))
        for u in con:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
            if u == T:
                return()
bfs(S,T)
#print(length)
if visit[T]:
    print(length[T])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v)
S, T = map(int, input().split())
S, T = S-1, T-1
def bfs3(v, n, ans):
    if n == 0:
        ans.append(v)
    else:
        for u in graph[v]:
            bfs3(u, n-1,ans)

visit = [False for i in range(N)]
length = [0 for i in range(N)]
def bfs(v, T):
    Q = []
    Q.append(v)
    visit[v] = True
    while len(Q) > 0:
        v = Q.pop(0)
        ans = []
        bfs3(v, 3, ans)
        con = list(set(ans))
        #print(con)
        for u in con:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
            if u == T:
                return()
bfs(S,T)
#print(length)
if visit[T]:
    print(length[T])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    graph[u].append(v)
S, T = map(int, input().split())
S, T = S-1, T-1
def bfs3(v, n, ans):
    if n == 0:
        ans.append(v)
    else:
        for u in graph[v]:
            bfs3(u, n-1,ans)

visit = [False for i in range(N)]
length = [0 for i in range(N)]
def bfs(v):
    Q = []
    Q.append(v)
    visit[v] = True
    while len(Q) > 0:
        v = Q.pop(0)
        ans = []
        bfs3(v, 3, ans)
        con = list(set(ans))
        #print(con)
        for u in con:
            if not visit[u]:
                visit[u] = True
                length[u] = length[v] + 1
                Q.append(u)
                #print(u, length[u])
bfs(S)
#print(length)
if visit[T]:
    print(length[T])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
visited = set()
queue = []
temp = []
def bfs(arr,jump):
    temp = []
    for node in arr:
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
        temp = temp+vertices[node]
    return temp
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
visited.add(s)
queue=deque()
queue.append([s,0])
while(len(queue)>0 ):
    next=queue.popleft()
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        bfs(vertices[next[0]], next[1])
print(max(jumpValue[t][0]//3,-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int,sys.stdin.readline().split())
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
visited = set()
queue = []
temp = []
def bfs(arr,jump):
    temp = []
    for node in arr:
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
        temp = temp+vertices[node]
    return temp
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
visited.add(s)
queue.append([s,0])
done =set()
while(len(queue)>0 ):
    next=queue.pop(0)
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        bfs(vertices[next[0]], next[1])
        bfs(temp, next[1] + 1)
        bfs(temp, next[1] + 2)
print(max(jumpValue[t][0]//3,-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int,sys.stdin.readline().split())
# sys.stdout.write('{} {}'.format(n,m))
vertices = [[] for _ in range(n+1)]
jumpValue = [[-1,-1,-1] for _ in range(n+1)]
visited = set()
queue = []
def bfs(arr,jump):
    temp = []
    for node in arr:
        # print('NODE:',node,jumpValue[node][(jump+1)%3])
        if jumpValue[node][(jump+1)%3]==-1:
            queue.append([node,jump+1])
            # queue.append(node)
        temp = temp+vertices[node]
        # if node==t:
        #     print('YES',jump+1)
        #     jumpValue[node].append(jump+1)
    return temp
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    vertices[a].append(b)
s,t = map(int,sys.stdin.readline().split())
visited.add(s)
queue.append([s,0])
# print(vertices)
done =set()
while(len(queue)>0 ):
    next=queue.pop(0)
    if jumpValue[next[0]][next[1]%3] == -1:
        jumpValue[next[0]][next[1]%3] = next[1]
        # print('Next:', next[0])
        # print(jumpValue)
        # print('Queue:', queue)
        # print('NEXT', next, vertices[next[0]])
        run = bfs(vertices[next[0]], next[1])
        run = bfs(run, next[1] + 1)
        bfs(run, next[1] + 2)
        # print('----------------------------------------------')
print(max(jumpValue[t][0]//3,-1))

Submission status: Time Limit Exceeded

Solution code:
#順探索
N, M = map(int, input().split())
E = []
for i in range(M):
    e = list(map(int, input().split()))
    E.append(e)
S, T = map(int, input().split())
keiro = [set()]
for i in range(N):
    keiro.append(set())
for e in E:
    keiro[e[0]].add(e[1])
step0p = set()
step0c = {S}
step1p = set()
step1c = set()
step2p = set()
step2c = set()
flag = 0 #flag = 0: 探索中 flag = 1: 解無し flag = 2:解発見
counter = 0
while flag == 0:
    for i in step0c:
        step1c = step1c | keiro[i]
    step1c = step1c - step1p
    step1p = step1p | step1c
    for i in step1c:
        step2c = step2c | keiro[i]
    step2c = step2c - step2p
    step2p = step2p | step2c
    for i in step2c:
        step0c = step0c | keiro[i]
    step0c = step0c - step0p
    step0p = step0p | step0c
    counter = counter + 1
    if step0c == set():
        flag = 1
    if {T} & step0c == {T}:
        flag = 2
if flag == 1:
    print(-1)
if flag == 2:
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
#順探索
N, M = map(int, input().split())
E = []
for i in range(M):
    e = list(map(int, input().split()))
    E.append(e)
S, T = map(int, input().split())
keiro = [set()]
for i in range(N):
    keiro.append(set())
for e in E:
    keiro[e[0]].add(e[1])
reached = {S}
before = set()
after = reached
flag = 0 #flag = 0: 探索中 flag = 1: 解無し flag = 2:解発見
counter = 0
while flag == 0:
    for i in range(3):
        before = after
        after = set()
        for b in before:
            after = after | keiro[b]
    counter = counter + 1
    if after - reached == set():
        flag = 1
    if {T} & after == {T}:
        flag = 2
    after = after - reached
    reached = reached | after
if flag == 1:
    print(-1)
if flag == 2:
    print(counter)

Submission status: Time Limit Exceeded

Solution code:
#逆探索
N, M = map(int, input().split())
E = []
for i in range(M):
    e = list(map(int, input().split()))
    e.reverse()
    E.append(e)
S, T = map(int, input().split())
keiro = []
for i in range(N):
    keiro.append(set())
for e in E:
    keiro[e[0]-1].add(e[1])
rireki = [{T}]
before = set()
after = {T}
flag = 0
while flag == 0:
    for i in range(3):
        before = after
        after = set()
        for b in before:
            after = after | keiro[b-1]
    after = after | rireki[-1]
    for r in rireki:
        if r == after:
            flag = 1
    if {S} & after == {S}:
        flag = 2
    rireki.append(after | rireki[-1])
    after = after - rireki[-2]
if flag == 1:
    print(-1)
if flag == 2:
    print(len(rireki)-1)

Submission status: Time Limit Exceeded

Solution code:
#逆探索
N, M = map(int, input().split())
E = []
for i in range(M):
    e = list(map(int, input().split()))
    e.reverse()
    E.append(e)
S, T = map(int, input().split())
keiro = []
for i in range(N):
    keiro.append(set())
for e in E:
    keiro[e[0]-1].add(e[1])
rireki = [{T}]
before = set()
after = {T}
flag = 0
while flag == 0:
    for i in range(3):
        before = after
        after = set()
        for b in before:
            after = after | keiro[b-1]
    for r in rireki:
        if r == after:
            flag = 1
    if {S} & after == {S}:
        flag = 2
    rireki.append(after | rireki[-1])
    after = after - rireki[-2]
if flag == 1:
    print(-1)
if flag == 2:
    print(len(rireki)-1)

Submission status: Time Limit Exceeded

Solution code:
#逆探索
N, M = map(int, input().split())
E = []
for i in range(M):
    e = list(map(int, input().split()))
    e.reverse()
    E.append(e)
S, T = map(int, input().split())
keiro = []
for i in range(N):
    keiro.append(set())
for e in E:
    keiro[e[0]-1].add(e[1])
rireki = [{T}]
before = set()
after = {T}
flag = 0
while flag == 0:
    for i in range(3):
        before = after
        after = set()
        for b in before:
            after = after | keiro[b-1]
    for r in rireki:
        if r == after:
            flag = 1
    if {S} & after == {S}:
        flag = 2
    rireki.append(after)
if flag == 1:
    print(-1)
if flag == 2:
    print(len(rireki)-1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
L1 = [set() for k in range(N+1)]
for k in range(M):
	u, v = map(int, input().split())
	L1[u].add(v)
S, T = map(int, input().split())
L2 = [None for k in range(N+1)]
L3 = [None for k in range(N+1)]
for n in range(N+1):
	a = set()
	for l in L1[n]:
		a = a.union(L1[l])
	L2[n] = a
	a = set()
	for l in L2[n]:
		a = a.union(L1[l])
	a.discard(n)
	L3[n] = a
t = 0
sumi = set([S])
now = set([S])
flg = 0
while(len(now) != 0):
	t +=1
	for d in now:
		now = now.union(L3[d])
	now = now - sumi
	sumi = sumi.union(now)
	if set([T]) <= sumi:
		print(t)
		flg = 1
		now = set()
if flg == 0:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

########

class Edge:
    def __init__(self, from_edge, to_edge, cost):
        self.from_edge = from_edge
        self.to_edge = to_edge
        self.cost = cost

def bellman_ford(start, edges, node_num):
    dist = [INF] * node_num
    dist[start] = 0
    flag = False # 負の閉路の有無
    for i in range(node_num):
        for edge in edges:
            if dist[edge.to_edge] > dist[edge.from_edge] + edge.cost:
                dist[edge.to_edge] = dist[edge.from_edge] + edge.cost
                if i == N-1:
                    flag = True
    return dist, flag

if __name__ == "__main__":
    # https://atcoder.jp/contests/abc016/tasks/abc016_3
    N, M = l_inpl()

    edges = []

    for _ in range(M):
        u, v = l_inpl()
        u, v = u-1, v-1
        edges.append(Edge(u, v+N, 1))
        edges.append(Edge(u+N, v+N*2, 1))
        edges.append(Edge(u+N*2, v, 1))

    S, T = l_inpl()
    S, T = S-1, T-1

    ans = bellman_ford(S, edges, N*3)[0][T]

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

Submission status: Time Limit Exceeded

Solution code:
import queue

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

V = [[0, 0, 0] for _ in range(N + 1)]
R = {}

for u, v in uv:
  if u not in R:
    R[u] = [v]
  else:
    R[u].append(v)
q = queue.Queue()
put = q.put
get = q.get

put([S, 0, 2])
ans = -1
while not q.empty():
  t = get()
  if t[0] == T and t[2] == 2:
    ans = t[1]
    break
  k = (t[2] + 1) % 3
  m = t[1]
  if t[2] == 2:
    m += 1
  if t[0] not in R: continue
  for i in R[t[0]]:
    if V[i][k] == 0:
      V[i][k] = 1
      put([i, m, k])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

if 0 == M:
	print(-1)
	exit()

s, t = S - 1, T - 1

graph = [[] for _ in range(N)]
for u, v in UV:
	graph[u - 1] += [v - 1]

INF = 10 ** 12
cost = [[INF, INF, INF] for _ in range(N)]
def print_cost(cost):
	for line in cost:
		for cell in line:
			print("  INF" if cell == INF else " {:4d}".format(cell), end="")
		print()
	print()

def dfs(graph, cost, c, d):
	if cost[c][d % 3] <= d:
		return
	cost[c][d % 3] = d
	#print_cost(cost)
	for n in graph[c]:
		dfs(graph, cost, n, d + 1)

dfs(graph, cost, s, 0)

if INF == cost[t][0]:
	print(-1)
else:
	print(cost[t][0] // 3)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
Dict = dict()
for x in range(1,N+1):
    Dict[str(x)] = set()

for x in range(M):
    u, v = input().split()
    Dict[u].add(v)
S, T = input().split()

memo = []
start = {S}
goal = T
step = 0

while True:
    step += 1
    for x in range(3):
        end = set()
        for x in start:
            for y in Dict[x]:
                end.add(y)
        start = end
    if goal in end:
        answer = step
        break
    elif end in memo:
        answer = -1
        break
    else:
        memo.append(end)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
# 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 = [[] for i in range(3)]
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
    nmod = (Now[1]+1)%3
    check[Now[1]].append(Now[0])
    for i in hen2[Now[0]-1]:
        if i not in check[nmod]:
            queue.append([i,nmod])
            dist.append(ndist+1)

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)
    two_steps_dict = defaultdict(list)
    for i in range(1, N+1):
        first_step = reversed_graph_dict[i]
        second_step = []
        for x in first_step:
            second_step += reversed_graph_dict[x]
        two_steps_dict[i] = list(set(second_step))

    for i in range(1, N+1):
        first_step = reversed_graph_dict[i]
        third_step = []
        added = set()
        for x in first_step:
            for y in two_steps_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()