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: Wrong Answer

Solution code:
from collections import deque
# 木構造を作る
N,M = map(int, input().split())

G = [[] for i in range(3*N)]
for i in range(M):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[3*(u-1)].append((3*(v-1)+1))
    G[3*(u-1)+1].append((3*(v-1)+2))
    G[3*(u-1)+2].append((3*(v-1)))

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

# 木をBFSをする
used = [-1] * (3*N)
# used[3*(S-1)] = 0 # 始めどこから行くか
q = deque([S-1])
while len(q) > 0:
    a = q.popleft()
    d = used[a]
    Vs = G[a]
    for u in Vs: # 頂点以外の要素がグラフにあるときはここ
        if used[u] == -1:
            q.append(u)
            used[u] = d+1
print(used[3*(T-1)]//3)

Submission status: Wrong Answer

Solution code:
from collections import deque
# 木構造を作る
N,M = map(int, input().split())

G = [[] for i in range(3*N)]
for i in range(M):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[3*(u-1)].append((3*(v-1)+1))
    G[3*(u-1)+1].append((3*(v-1)+2))
    G[3*(u-1)+2].append((3*(v-1)))

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



# 木をBFSをする
used = [-1] * (3*N)
used[3*(S-1)] = 0 # 始めどこから行くか
q = deque([S-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    d = used[a]
    Vs = G[a]
    for u in Vs: # 頂点以外の要素がグラフにあるときはここ
        if used[u] == -1:
            q.append(u)
            used[u] = d+1
if used[3*(T-1)] % 3 != 0:
    print(-1)
else:
    print(used[3*(T-1)]//3)

Submission status: Wrong Answer

Solution code:
from collections import deque
# 木構造を作る
N,M = map(int, input().split())

G = [[] for i in range(3*N)]
for i in range(M):
    # グラフに頂点を追加(距離があるときは,u,vの後に入れる)
    u,v = map(int,input().split())
    G[3*(u-1)].append((3*(v-1)+1))
    G[3*(u-1)+1].append((3*(v-1)+2))
    G[3*(u-1)+2].append((3*(v-1)))

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



# 木をBFSをする
used = [-1] * (3*N)
used[3*(S-1)] = 0 # 始めどこから行くか
q = deque([S-1])
cnt = 0
while len(q) > 0:
    a = q.popleft()
    d = used[a]
    Vs = G[a]
    for u in Vs: # 頂点以外の要素がグラフにあるときはここ
        if used[u] == -1:
            q.append(u)
            used[u] = d+1

print(used[3*(T-1)]//3)

Submission status: Wrong Answer

Solution code:
"""
めも
有向グラフを構築したあと、それを距離3の点でもう一回つなぎ直したグラフを構築して、最短経路を考えればよさそう
でも有向グラフってどうやって実装するんだろう〜〜〜
"""

N, M = map(int, input().split())
p = []
for i in range(M):
	p.append(list(map(int, input().split())))
# print("p", p)
S, T = map(int, input().split())

g = [[] for i in range(N + 1)]
for pi in p:
	g[pi[0]].append(pi[1])
# print("g", g)

G = [[] for i in range(N + 1)]
# 3つ移動した先を格納するグラフがG（これが本問における実質的な移動）
for i in range(1, N + 1):
	for e in g[i]:
		for f in g[e]:
			for h in g[f]:
				G[i].append(h)
# print("G", G)

# G[1]→G[6]の最短距離をもとめる→ダイクストラ法を使ってみる

cost = [float("inf") for _ in range(N + 1)]
now = S  # 現在居る頂点をnowとする
seen = []  # seenはnowから辿れる未探索の頂点
cost[S] = 0  # 初期値は0

for now in range(1, N + 1):
	# seenに追加
	for i in G[now]:
		seen.append(i)
	# 更新
	for i in seen:
		cost[i] = min(cost[i], cost[now] + 1)
	seen = []  # 探索完了したのでseenをリセット

if cost[T] == float("inf"):
	print(-1)
else:
	print(cost[T])

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
mod=10**9+7
Layer=[]
a=1
b=1
while(b<=N):
    a=b
    b=N//(N//a)+1
    Layer.append((a,b))
#print(Layer)
num=[x[1]-x[0] for x in Layer]
M=len(Layer)
#print(num)
dp=[[0 for j in range(M+1)] for i in range(K+1)]
dp[0][0]=1
sdp=[0 for i in range(M+2)]
for k in range(K):
    for j in range(M+1):
        sdp[j+1]=(dp[k][j]+sdp[j])%mod
    for j in range(M):
        dp[k+1][j]=(sdp[M-j]*num[j])%mod
ans=0
for j in range(M+1):
    ans+=dp[K][j]
    ans%=mod
print(ans)

Submission status: Wrong Answer

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

N,M=map(int,input().split())
E=[list(map(int,input().split())) for i in range(M)]
S,G=map(int,input().split())

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

for x,y in E:
    ELIST[x].append(y)

DIS=[[-1,-1,-1] for i in range(N+1)]
DIS[1][0]=0

from collections import deque

S=deque([S])
i=1

while S:
    #print(S)
    NEWS=deque()
    while S:     
        x=S.pop()

        for to in ELIST[x]:
            if DIS[to][i%3]==-1:
                DIS[to][i%3]=i
                NEWS.append(to)

    i+=1
    S=NEWS

print(DIS[G][0]//3)

Submission status: Wrong Answer

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

n,k = m()

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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


print(BC132_E())

Submission status: Wrong Answer

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


print(BC132_E())

Submission status: Wrong Answer

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

n,k = m()

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]
#N = int(input())

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

S, T = [int(i) for i in input().split()]
d1 = Dijkstra(g, (S-1)*3)
ans = 0
if d1.dist[(T-1)*3] != float("inf"):
    print(d1.dist[(T-1)*3]//2)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]
#N = int(input())

for i in range(M):
    u, v = [int(i) for i in input().split()]
    print(u, v)
    u -= 1
    v -= 1
    g.add_edge(3*u+0, 3*v+1, 1)
    g.add_edge(3*u+1, 3*v+2, 1)
    g.add_edge(3*u+2, 3*v+0, 1)

S, T = [int(i) for i in input().split()]
d1 = Dijkstra(g, (S-1)*3)
ans = 0
if d1.dist[(T-1)*3] != float("inf"):
    print(d1.dist[(T-1)*3]//2)
else:
    print(-1)

Submission status: Wrong Answer

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

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

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

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

# T = [[0] * N for _ in range(N)]
E = [set() for _ in range(N + 1)]

for i in range(M):
    u, v = [int(x) for x in input().split()]
    E[u].add(v)

S, T = [int(x) for x in input().split()]


def f(s, e):
    ret = set()
    for ne in e[s]:
        ret.add(ne)
    return ret


E2 = [set() for _ in range(N + 1)]
for i in range(N + 1):
    for t in f(i, E):
        for t2 in f(t, E):
            E2[i].add(t2)

E3 = [set() for _ in range(N + 1)]
for i in range(N + 1):
    for t in f(i, E2):
        for t2 in f(t, E):
            E3[i].add(t2)

openNodes = {S}
closeedNodes = {}
mi = [INF] * (N + 1)
mi[S] = 0

while len(openNodes) != 0:
    curNode = -1
    curW = INF
    for on in openNodes:
        if mi[on] < curW:
            curNode = on
    openNodes.remove(curNode)

    for nn in E3[curNode]:
        if mi[nn] == INF:
            openNodes.add(nn)
            mi[nn] = mi[on] + 1

print(mi[T] if mi[T] != INF else -1)

Submission status: Wrong Answer

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

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

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

INF = 10**10
d = [INF for i in range(3*N)]

que = []
d[0] = 0
heapq.heappush(que, [0, 0])

while not(len(que) == 0):
    q = heapq.heappop(que)
    ver = q[1]
    dis = q[0]

    if d[ver] < dis:
        continue

    for i in range(len(G[ver])):
        e = G[ver][i]
        if d[e[0]] > d[ver] + e[1]:
            d[e[0]] = d[ver] + e[1]
            heapq.heappush(que, [d[e[0]], e[0]])

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

def dfs(v,t,c):
  if c%3==0 and v==t:
    return c//3
  if check[v][c%3]==1:
    return 10**10
  check[v][c%3]=1
  ans=10**10
  for i in g[v]:
    ans=min(ans,dfs(i,t,c+1))
  return ans
        
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
s,t=map(int,input().split())
check=[[0]*3 for _ in range(n+1)]
ret=dfs(s,t,0)
if ret==10**10:
  print(-1)
else:
  print(ret)

Submission status: Wrong Answer

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

import time

def main(): 
    start = time.time()

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

    # print(reversed_graph_dict)

    import collections
    def bfs(graph, root):
        seen, queue = set([root]), collections.deque([[root, 0],])
        while queue:
            vertex, tries = queue.popleft()
            tries += 1

            # 三段先を見に行く。
            first_step = graph[vertex]
            second_step = []
            for x in first_step:
                second_step += graph[x]
            third_step = []
            for x in set(second_step):
                third_step += graph[x]

            for node in set(third_step):
                if node == S:
                    print(tries)
                    return
                if node not in seen:
                    seen.add(node)
                    queue.append([node, tries])
            if (time.time() - start) > 1.6:
                print(-1)
                return
        print(-1)
        return

    bfs(reversed_graph_dict, T)


main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())

graph1 = [[] for _ in range(n*3)]

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph1[u*3+0].append(v*3+1)
    graph1[u*3+1].append(v*3+2)
    graph1[u*3+2].append(v*3+0)

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


from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    NextCost = 1
    while heap:
        cost,thisNode = heappop(heap)
        for NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
    # dist = [costs to nodes]

inf = float('inf')
dist = dijkstra(graph1, n*3, s)
if dist[t] == inf:
    print(-1)
else:
    print(dist[t])

Submission status: Wrong Answer

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

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


point_list = [s]
for i in range(n):
    new_point_list = []
    for j in point_list:
        new_point_list += new_connect_list[j]
    new_point_list = list(set(new_point_list))
    point_list = new_point_list
    if t in point_list:
        print(i+1)
        break

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())

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

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist
S,T = map(int,input().split())
dij = dijkstra(g,3*N,S-1)
ans = dij[T-1]//3
if ans == float('inf') or M==0:
    ans = -1

print(ans)

Submission status: Wrong Answer

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

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

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

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

# T = [[0] * N for _ in range(N)]
E = [set() for _ in range(N + 1)]

for i in range(M):
    u, v = [int(x) for x in input().split()]
    E[u].add(v)

S, T = [int(x) for x in input().split()]


def f(startSet, n):
    if n == 0:
        return startSet
    ret = set()
    for s in startSet:
        for t in E[s]:
            ret.add(t)
    return f(ret, n - 1)


# print(f({1}, 3))
# print(f({2}, 3))
# print(f({3}, 3))
# print(f({4}, 3))

E2 = [f({i}, 3) for i in range(N + 1)]

openNodes = {S}
closeedNodes = {}
mi = [INF] * (N + 1)
mi[S] = 0

while len(openNodes) != 0:
    curNode = -1
    curW = INF
    for on in openNodes:
        if mi[on] < curW:
            curNode = on
    openNodes.remove(curNode)

    for nn in E2[curNode]:
        if mi[nn] == INF:
            openNodes.add(nn)
            mi[nn] = mi[on] + 1

print(mi[T] if mi[T] != INF else -1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]

inputs=[]
n,m=map(int,input().split())
for i in range(m):
    a=[int(j) for j in input().split()]
    inputs.append((a[0],a[1],1))
S,T=map(int,input().split())

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    g.add_edge(dst, src, weight)

d = Dijkstra(g, S)   
ans=d.shortest_distance(T)

if ans>10**9+7:
    print(ans)
else:
    if ans%3==0:
        print(ans//3)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
edge_to = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    edge_to[u-1].append(v-1)
S, T = map(int,input().split())
S -= 1
T -= 1
dest = [set() for i in range(N)]
def find_dest(i, j, cnt): #けんけんぱで行けるところ
    if cnt == 3:
        dest[i].add(j)
        return
    for k in edge_to[j]:
        find_dest(i, k, cnt+1)
for i in range(N):
    find_dest(i, i, 0)
q = [(S, 0)]
visited = [False for i in range(N)]
visited[S] = True
while q != []:
    now, cnt = q.pop(0)
    for j in dest[now]:
        if j == T:
            print(now, cnt)
            print(cnt+1)
            exit(0)
        if not visited[j]:
            q.append((j, cnt+1))
            visited[j] = True
print(-1)

Submission status: Wrong Answer

Solution code:
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}
    ans=0
    while n:
        tmp=set()
        p=w
        n-=1
        ans+=1
        for i in p:
            if i in d:
                for j in d[i]:
                    tmp.add(j)
        if t in tmp and ans%3==0:
            print(ans//3)
            exit()
        w=tmp
    print(-1)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))
d = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  d[u].add(v)
s, t = list(map(int, input().split()))

def bfs():
  que = [(s, 0, 0)]
  visited = set()

  while len(que) > 0:
    p = que.pop(0)
    if p[0]==t and p[2]==2:
      return p[1]
    if p[0] in visited:
      continue
    for nx in d[p[0]]:
      que.append((nx, p[1]+1, (p[2]+1)%3))
    visited.add(p[0])
  return -1

print(bfs())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))
d = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  d[u].add(v)
s, t = list(map(int, input().split()))

def bfs():
  que = [(s, 0, 0)]
  visited = set()

  while len(que) > 0:
    p = que.pop(0)
    if p[0]==t and p[2]==2:
      return p[1]
    if p in visited:
      continue
    visited.add(p)
    for nx in d[p[0]]:
      que.append((nx, p[1]+1, (p[2]+1)%3))
  return -1

print(bfs())

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=[[] for i in range(3*N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    G[3*u+0].append(3*v+1)
    G[3*u+1].append(3*v+2)
    G[3*u+2].append(3*v+0)
S,T=map(int,input().split())
INF=10**9+7
def dijkstra(G,s):

  d=[INF]*(3*N)
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node in G[v]:
      cost=1
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d
d=dijkstra(G,(S-1)*3)
if d[(T-1)*3+2]==INF:
  print(-1)
else:
  print(d[(T-1)*3+2])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n, m = list(map(int, input().split()))
d = defaultdict(set)
for i in range(m):
  u, v = list(map(int, input().split()))
  d[u].add(v)
s, t = list(map(int, input().split()))

def bfs():
  que = [(s, 0, 0)]
  visited = set()

  while len(que) > 0:
    p = que.pop(0)
    if p[0]==t and p[2]==2:
      return p[1]
    for nx in d[p[0]]:
      if nx in visited:
        continue
      visited.add(nx)
      que.append((nx, p[1]+1, (p[2]+1)%3))
  return -1

print(bfs())