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:
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 visited[v]:
            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: Wrong Answer

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 visited[v]:
            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: Wrong Answer

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 = 5 * 10 ** 5
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 visited[v]:
            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: Wrong Answer

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 queue != []:
    Now = queue.pop(0)
    if Now[2]>10**15:
        print(-1)
        break
    if Now[0]==T and Now[1]==0:
        print(int(Now[2]/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,Now[2]+1])
if queue == []:
    print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from heapq import heappop, heappush
from copy import deepcopy

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [[INF] * N for i in range(3)]
    # スタート位置
    que = [(0, 0, src)]
    res[0][src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # 現在のノード
        _, k, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxtk, nxt in nodes[k][cur]:
            # 今回の経路のが短い時
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxtk][nxt], nxtk, nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1

# 元の頂点を3層に拡張する
nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=dijkstra(N, nodes2, S)
if res[0][T]==INF:
    print(-1)
else:
    print(res[0][T])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from heapq import heappop, heappush
from copy import deepcopy

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
    """ ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [[INF] * N for i in range(3)]
    # スタート位置
    que = [(0, 0, src)]
    res[0][src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # 現在のノード
        _, k, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxtk, nxt in nodes[k][cur]:
            # 今回の経路のが短い時
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxtk][nxt], nxtk, nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1

# 元の頂点を3層に拡張する
nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=dijkstra(N, nodes2, S)
if res[2][T]==INF:
    print(-1)
else:
    print(res[2][T])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from heapq import heappop, heappush

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点)
def dijkstra(N: int, nodes: list, src: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [[INF] * N for i in range(3)]
    # スタート位置
    que = [(0, src)]
    res[0][src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # 現在のノード
        k, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxtk, nxt in nodes[k][cur]:
            # 今回の経路のが短い時
            if res[k][cur] + 1 < res[nxtk][nxt]:
                res[nxtk][nxt] = res[k][cur] + 1
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (nxtk, nxt))
    # ノードsrcからの最短距離リストを返却
    return res

N,M=MAP()
nodes=[[] for i in range(N)]
for i in range(M):
    u,v=MAP()
    nodes[u-1].append(v-1)
S,T=MAP()
S-=1
T-=1

# 元の頂点を3層に拡張する
nodes2=[[[] for j in range(N)] for i in range(3)]
for i in range(3):
    for u, node in enumerate(nodes):
        for v in node:
            nodes2[i][u].append(((i+1)%3, v))

res=dijkstra(N, nodes2, S)
if res[2][T]==INF:
    print(-1)
else:
    print(res[2][T])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from scipy.misc import comb

n, k = map(int, input().split())

mod = int(10 ** 9 + 7)

for i in range(1, k + 1):
    if i > n - k + 1:
        print(0)
    else:
        print(comb(k - 1, i - 1) * comb(n - k + 1, i) % mod)

Submission status: Wrong Answer

Solution code:
from itertools import chain


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

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


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


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

visited = [0 for _ in range(n + 1)]
cost = 0
st = [(s, 0)]
ans = -1
pre = None
while len(st):
    pos, cost = st.pop()
    visited[pos] = 1
    if pos == t:
        ans = cost
        break
    for n in find_next(pos, edges):
        if visited[n] == 0:
            st.append((n, cost + 1))

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict



class Graph:

  def __init__(self,N,uv,S,T):
    self.graph = uv
    self.start = S
    self.goal = T
    self.states  = [[-3 for _ in range(3)] for _ in range(N)]
    self.states[self.start][0] = 0

  def solve(self):
    nxt = {self.start}
    ## update
    while len(nxt) > 0:
      p = nxt.pop()
      for q in self.graph[p]:
        for ps in range(3):
          if self.states[p][ps] >= 0:
            qs = (ps+1)%3
            if self.states[q][qs] < 0:
              self.states[q][qs] = self.states[p][ps]+1
              nxt.add(q)
            else:
              self.states[q][qs] = min(self.states[q][qs],self.states[p][ps]+1)
    ## return
    return self.states[self.goal][0]


def main():
  ## input
  N,M = map(int, input().split())
  uv = defaultdict(set)
  for _ in range(M):
    u,v = map(int, input().split())
    uv[u-1].add(v-1)
  S,T = map(int, input().split())

  ## solve
  graph = Graph(N,uv,S-1,T-1)
  print(graph.solve()//3)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict



class Graph:

  def __init__(self,N,uv,S,T):
    self.graph = uv
    self.start = S
    self.goal = T
    self.states  = [[-1 for _ in range(3)] for _ in range(N)]
    self.states[self.start][0] = 0

  def solve(self):
    nxt = {self.start}
    ## update
    while len(nxt) > 0:
      p = nxt.pop()
      for q in self.graph[p]:
        for ps in range(3):
          if self.states[p][ps] >= 0:
            qs = (ps+1)%3
            if self.states[q][qs] < 0:
              self.states[q][qs] = self.states[p][ps]+1
              nxt.add(q)
            else:
              self.states[q][qs] = min(self.states[q][qs],self.states[p][ps]+1)
    ## return
    if self.states[self.goal][0] >= 0:
      return self.states[self.goal][0]
    else:
      return -3


def main():
  ## input
  N,M = map(int, input().split())
  uv = defaultdict(set)
  for _ in range(M):
    u,v = map(int, input().split())
    uv[u-1].add(v-1)
  S,T = map(int, input().split())

  ## solve
  graph = Graph(N,uv,S-1,T-1)
  print(graph.solve()//3)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict



class Graph:

  def __init__(self,N,uv,S,T):
    self.graph = uv
    self.start = S
    self.goal = T
    self.states  = [[-1 for _ in range(3)] for _ in range(N)]
    self.states[self.start][0] = 0

  def solve(self):
    nxt = {self.start}
    visited = set([])
    while len(nxt) > 0 and len(visited) < len(self.states):
      p = nxt.pop()
      ## return
      if self.states[self.goal][0] >= 0:
        return self.states[self.goal][0]

      ## update
      for q in self.graph[p]:
        for ps in range(3):
          if self.states[p][ps] >= 0:
            qs = (ps+1)%3
            if self.states[q][qs] < 0:
              self.states[q][qs] = self.states[p][ps]+1
              nxt.add(q)
            else:
              self.states[q][qs] = min(self.states[q][qs],self.states[p][ps]+1)
    return -3


def main():
  ## input
  N,M = map(int, input().split())
  uv = defaultdict(set)
  for _ in range(M):
    u,v = map(int, input().split())
    uv[u-1].add(v-1)
  S,T = map(int, input().split())

  ## solve
  graph = Graph(N,uv,S-1,T-1)
  print(graph.solve()//3)


if __name__ == "__main__":
  main()

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 collections
import heapq

class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)


    def add(self, u, v, d, directed=False):
        """
        0-indexedでなくてもよいことに注意
        u = from, v = to, d = cost
        directed = Trueなら、有向グラフである
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])


    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]


    def Dijkstra_search(self, s):
        """
        0-indexedでなくてもよいことに注意
        s = 始点
        return: 始点から各点までの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:  # DefaulfではFalseとなる
                continue


            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))


        return d



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

    dij = Dijkstra()

    # 三段先のグラフを先に作っておく。
    three_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]
        third_step = []
        for x in set(second_step):
            for y in set(reversed_graph_dict[x]):
                dij.add(i,y,1,directed=True)

    print(dij.Dijkstra_search(s=T)[S])



main()

Submission status: Wrong Answer

Solution code:
import heapq
N, M = map(int, input().split())
Edge = [list(map(int, input().split())) for i in range(M)]

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


G3 = [[] for i in range(3 * N)]
for u, v in Edge:
    u, v = u - 1, v - 1
    G3[u].append([v + N, 1])
    G3[u + N].append([v + N * 2, 1])
    G3[u + 2 * N].append([v, 1])


def dijkstra(x):
    d = [float('inf')] * (3 * N)
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G3[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u] + cost, node))
    return d


dist = dijkstra(S)
print(dist[T + 2 * N] if dist[T + 2 * N] != float('inf') else - 1)

Submission status: Wrong Answer

Solution code:
import heapq
N, M = map(int, input().split())
Edge = [list(map(int, input().split())) for i in range(M)]

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


G3 = [[] for i in range(3 * N)]
for u, v in Edge:
    u, v = u - 1, v - 1
    G3[u].append([v + N, 1])
    G3[u + N].append([v + N * 2, 1])
    G3[u + 2 * v].append([v, 1])


def dijkstra(x):
    d = [float('inf')] * (3 * N)
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G3[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u] + cost, node))
    return d


dist = dijkstra(S)
print(dist[T + 2 * N] if dist[T + 2 * N] != float('inf') else - 1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        G[u-1].append(v-1)
    S, T = map(int, input().split())
    S, T = S-1, T-1

    q = deque()
    q.append(S)
    cnt = 0
    cnt_k = 0
    visited = [False] * N
    visited[S] = True
    while len(q) > 0:
        cnt += 1
        if cnt % 3 == 0:
            cnt_k += 1

        while len(q) > 0:
            n0 = q.pop()
            next_ = set()
            for n1 in G[n0]:
                if cnt % 3 == 0:
                    if n1 == T:
                        return cnt_k
                    visited[n1] = True

                if visited[n1]:
                    continue

                next_.add(n1)

        q = deque()
        q.extend(list(next_))

    return -1


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import heapq

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

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


depth_3_edge = [[] for i in range(N)]


for n in range(N):
    visited = [0] * N
    visited[n] = 1

    stack = [(n, 0)]
    while stack:
        fr, depth = stack.pop()
        if depth > 3:
            continue

        for to in G[fr]:
            if visited[to] == 3:
                continue

            visited[to] += 1

            stack.append((to, depth + 1))
            if depth == 2:
                depth_3_edge[n].append((to, 1))


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in depth_3_edge[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


dist = dijkstra(S)
print(dist[T] if dist[T] != float('inf') else -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()]

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

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

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


def bfs(e, start, end):
    open = [start]
    w = dict()
    w[start] = 0
    while len(open) != 0:
        target = open.pop()
        for next in E[target]:
            if not next in w:
                open.append(next)
                w[next] = w[target] + 1

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


print(bfs(E, S, T))

Submission status: Wrong Answer

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

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA, self), BridgeEdge(nodeB, self)]
        nodeA.addEdge(self.edges[1])
        #nodeB.addEdge(self.edges[0])

class BridgeEdge:
    def __init__(self, node, edge):
        self.edge = edge
        self.node = node
        self.flag = 0

class Node:
    def __init__(self, id):
        self.id = id
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)
    def __repr__(self):
        return "({}, {:b})".format(self.id, self.flag)

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

for ui, vi in (map(int, input().split()) for _ in range(M)):
    Bridge(nodes[ui], nodes[vi])

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

#nodes[S].flag = 1
s = [(None, nodes[S], 0)]
idx = 0
isOK = False
while idx < len(s):
    pre, cur, level = s[idx]
    idx += 1
    nxtlevel = level + 1
    nxtflag = 1 << (nxtlevel % 3)

    for nxt in cur.bridges:
        if not pre is nxt.node:
            if (nxt.flag & nxtflag) == 0:
                nxt.flag |= nxtflag 
                if nxt.node is nodes[T] and nxtflag == 1:
                    isOK = True
                    break
                s.append((cur, nxt.node, nxtlevel))
    else:
        continue
    break
if isOK:
    print(nxtlevel//3)
else:
    print(-1)

Submission status: Wrong Answer

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

class Bridge:
    def __init__(self, nodeA, nodeB):
        self.edges = [BridgeEdge(nodeA, self), BridgeEdge(nodeB, self)]
        nodeA.addEdge(self.edges[1])
        nodeB.addEdge(self.edges[0])

class BridgeEdge:
    def __init__(self, node, edge):
        self.edge = edge
        self.node = node

class Node:
    def __init__(self, id):
        self.id = id
        self.flag = 0
        self.bridges = []
    def addEdge(self, bridgeEdge):
        self.bridges.append(bridgeEdge)
    def __repr__(self):
        return "({}, {:b})".format(self.id, self.flag)

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

for ui, vi in (map(int, input().split()) for _ in range(M)):
    Bridge(nodes[ui], nodes[vi])

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

nodes[S].flag = 1
s = [(None, nodes[S], 0)]
idx = 0
isOK = False
while idx < len(s):
    pre, cur, level = s[idx]
    idx += 1
    nxtlevel = level + 1
    nxtflag = 1 << (nxtlevel % 3)

    for nxt in cur.bridges:
        if not pre is nxt.node:
            if (nxt.node.flag & nxtflag) == 0:
                nxt.node.flag |= nxtflag 
                if nxt.node is nodes[T] and nxtflag == 1:
                    isOK = True
                    break
                s.append((cur, nxt.node, nxtlevel))
    else:
        continue
    break
if isOK:
    print(nxtlevel//3)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import collections


def main():
    n, m = [int(s) for s in sys.stdin.readline().strip().split()]
    graph = collections.defaultdict(set)
    for _ in range(m):
        u, v = [int(s) for s in sys.stdin.readline().strip().split()]
        graph[u].add(v)
    s, t = [int(s) for s in sys.stdin.readline().strip().split()]

    shortest = dict()
    shortest[s] = 0
    q = collections.deque()
    q.append((0, s, 0))
    seen = dict()
    while q:
        level, loc, turn = q.pop()
        children = graph[loc]
        child_turn = turn + 1
        child_level = (level+1) % 3
        for child in children:
            if (child_level, child) not in seen:
                if child_level == 0 and child == t:
                    print(child_turn // 3)
                    return
                seen[(child_level, child)] = child_turn
                q.append((child_level, child, child_turn))

    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200000)
def main():
    INF = float("inf")
    input = sys.stdin.readline
    N, M = map(int,input().split())
    G = [[] for k in range(N)]
    for k in range(M):
        u, v = map(int,input().split())
        u -= 1
        v -= 1
        G[u] += [v]
    S, T = map(int,input().split())
    S -= 1
    T -= 1
    D = [[INF,INF,INF] for k in range(N)]
    D[S][0] = 0
    def dfs(now,k):
        for tsugi in G[now]:
            if D[tsugi][(k+1)%3] > D[now][k%3] + 1:
                D[tsugi][(k+1)%3] = D[now][k%3] + 1
                dfs(tsugi,k+1)

    dfs(S,0)
    if D[T][2] == INF:
        print(-1)
    else:
        print(D[T][2])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
MAX= 10**5+5
INF= 10**9
def resolve():
    n,m = map(int,input().split())
    net = [[] for i in range(MAX)]
    vn = [[INF]*3 for i in range(n+1)]
    for i in range(m):
        u,v = map(int,input().split())
        net[u].append(v)
    s,t = map(int,input().split())
    vn[s][0]=0
    q = deque()
    q.append((s,0))
    while q:
        v = q.pop()
        vs = v[0]
        vd = v[1]
        nd=(vd+1)%3
        for u in net[vs]:
            if vn[u][nd]==INF:
                vn[u][nd] = vn[vs][vd]+1
                q.append((u,nd))
    ans = vn[t][0]
    if( ans==INF):
        print(-1)
    else:
        print(ans//3)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
MAX= 10**5+5
INF= 10**9
def resolve():
    n,m = map(int,input().split())
    net = [[] for i in range(MAX)]
    vn = [[INF]*3 for i in range(n+1)]
    for i in range(m):
        u,v = map(int,input().split())
        net[u].append(v)
    s,t = map(int,input().split())
    vn[s][0]=0
    q = [(s,0)]
    while q:
        v = q.pop(-1)
        vs = v[0]
        vd = v[1]
        nd=(vd+1)%3
        for u in net[vs]:
            if vn[u][nd]==INF:
                vn[u][nd] = vn[vs][vd]+1
                q.append((u,nd))
    ans = vn[t][0]
    if( ans==INF):
        print(-1)
    else:
        print(vn[t][0]//3) 

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

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

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

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

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

if M == 0:
    print(-1)
    exit()
# 木をBFSをする
used = [-1] * (3*N)
used[3*(S-1)] = 0
q = deque([S-1])
while q:
    v = q.popleft()
    d = used[v]
    d += 1
    Vs = G[v]
    for u in Vs:
        if used[u] > 0:
            continue
        else:# 自分も含める
            q.append(u)
            used[u] = d
        if u == 3*(T-1):
            break

ans = used[3*(T-1)]
print(-1 if ans == -1 else ans//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])
while q:
    v = q.popleft()
    d = used[v]
    d += 1
    Vs = G[v]
    for u in Vs:
        if used[u] == -1 or used[u] == 0:# 自分も含める
            q.append(u)
            used[u] = d

ans = used[3*(T-1)]
print(-1 if ans == -1 else ans//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])
while len(q) > 0:
    a = q.popleft()
    d = used[a]
    Vs = G[a]
    # print("{}-{} : {}".format(a//3+1,a%3,d))
    for u in Vs: # 頂点以外の要素がグラフにあるときはここ
        if used[u] == -1 or used[u] == 0: # 自分も含める
            q.append(u)
            used[u] = d+1
print(used[3*(T-1)]//3)