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: Runtime Error

Solution code:
from queue import Queue
import heapq
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(x): print(x, file=sys.stderr)
# template


class Graph():
    """
    Graph のテンプレート。デフォルトは重みなしの有向グラフの隣接リスト形式での定義。
    Parameters
    --------
        n (int): グラフのサイズ。
    Options
    --------
        Weighted = False: 重み付きかどうか
        Directed = True: 有向かどうか
        Matrix = False:　グラフの表現を隣接リストにするか隣接行列にするか。デフォルトは隣接リスト。
    Methods
    -------
        add_edge(start,end,(weight))
            start から end に重さ weight の辺を張る。重みなしグラフの場合は weight を省略する。
        dijkstra(start): O((E+V)logV)
            start から各頂点への最短距離を返す。負の辺があると無理。
        bellman_ford(start): O(EV)
            start から各頂点への最短距離を返す。負の辺があってもいけるが遅い。
    """

    def __init__(self, n, Weighted=False, Directed=True, Matrix=False):
        self.sz = n
        self.is_Weighted = Weighted
        self.is_Directed = Directed
        self.is_Matrix = Matrix
        if Matrix:
            if Weighted:
                self.graph = [[float('inf') for _i in range(n)]
                              for _j in range(n)]
            else:
                self.graph = [[0 for _i in range(n)] for _j in range(n)]
        else:
            self.graph = [[] for _i in range(n)]

    def _weighted_add_edge(self, x, y, w):
        if self.is_Matrix:
            self.graph[x][y] = w
        else:
            self.graph[x].append((y, w))

    def _unweighted_add_edge(self, x, y):
        if self.is_Matrix:
            self.graph[x][y] = 1
        else:
            self.graph[x].append(y)

    def add_edge(self, x, y, *w):
        if self.is_Directed:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
            else:
                self._unweighted_add_edge(x, y)
        else:
            if self.is_Weighted:
                self._weighted_add_edge(x, y, w[0])
                self._weighted_add_edge(y, x, w[0])
            else:
                self._unweighted_add_edge(x, y)
                self._unweighted_add_edge(y, x)

    def _convert_to_maxrix(self):
        if self.is_Matrix:
            return self
        mat_g = self.__class__(
            self.sz,
            Weighted=self.is_Weighted,
            Directed=self.is_Directed,
            Matrix=True)
        if self.is_Weighted:
            for i in range(self.sz):
                for j in self.graph[i]:
                    mat_g.add_edge(i, j[0], j[1])
        else:
            for i in range(self.sz):
                for j in self.graph[i]:
                    mat_g.add_edge(i, j)
        return mat_g

    def __getitem__(self, n):
        return self.graph[n]

    # def __setitem__(self, n, v):
    #     if not self.is_Weighted and not self.is_Matrix:
    #         self.graph[n] = v

    def __str__(self):
        return str([self.graph[i] for i in range(self.sz)])

    def dijkstra(self, s):
        """
        単一始点最短距離を求める関数。dijkstra(s)でsからの任意の頂点への最短距離を求める。到達できなければfloat('inf')を返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならば bfs を使うか，グラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
        """
        if self.is_Matrix:
            print("隣接リスト形式で入力してください")
            raise TypeError
        d = [float('inf') for _ in range(self.sz)]
        b = [-1 for _ in range(self.sz)]  # 最短経路で各頂点の直前を表す list （経路復元）
        q = []
        d[s] = 0
        heapq.heappush(q, (d[s], s))
        while not len(q) == 0:
            p = heapq.heappop(q)
            v = p[-1]
            if d[v] < p[0]:
                continue
            # if self.is_Weighted:
            for e in self.graph[v]:
                u = e[0]
                c = e[-1]
                if d[u] > d[v] + c:
                    d[u] = d[v] + c
                    b[u] = v
                    heapq.heappush(q, (d[u], u))
            # else:
            #     for e in self.graph[v]:
            #         u = e
            #         if d[u] > d[v] + 1:
            #             d[u] = d[v] + 1
            #             b[u] = v
            #             heapq.heappush(q, (d[u], u))
        return d

    def bellman_ford(self, s):
        """
        単一始点最短距離を求める関数。bellman_ford(s)でsからの任意の頂点への最短距離を求める。到達できなければ　float('inf')　を返す。負のサイクルがある場合は False のみを返す。

        Warning
        ----------
            隣接リスト形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = [float('inf') for _ in range(self.sz)]
        d[s] = 0
        for i in range(self.sz - 1):
            for v in range(self.sz):
                for e in self.graph[v]:
                    u = e[0]
                    c = e[-1]
                    if d[v] == float('inf'):
                        continue
                    d[u] = min(d[u], d[v] + c)
        for v in range(self.sz):
            for e in self.graph[v]:
                u = e[0]
                c = e[-1]
                if d[v] == float('inf'):
                    continue
                if d[u] > d[v] + c:
                    return False
        return d

    def warshall_froyd(self):
        """
        全頂点間最短距離を求める関数。warshall_froyd()で任意の頂点間の最短距離を求める。到達できなければ　float('inf')　を返す。
        負のサイクルがあるかどうかは自分自身との最短距離 d[i][i] の中に負のものがあるかどうかで分かる。

        Warning
        ----------
            隣接行列形式の重み付きグラフにしか対応していないので注意すること。重みなしグラフならばグラフ構築時にあらかじめ重み　1　にしておく。
        Parameters
        ----------
            s (int): 最短距離を求める start の頂点
        Returns
        ----------
            d (list): d[i] に start から i までの最短距離の入った list
            または
            False: 負のサイクルがある場合
        """
        d = self._convert_to_maxrix()
        for i in range(self.sz):
            d[i][i] = 0
        for k in range(self.sz):
            for i in range(self.sz):
                for j in range(self.sz):
                    if d[i][k] != float('inf') and d[k][j] != float('inf'):
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d


def AOJ_ALDS_1_11_A():
    """
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A&lang=jp
    """
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    mat_g = g._convert_to_maxrix()
    for i in range(n):
        print(*mat_g[i])
# verified on 2019/07/02


def AOJ_ALDS_1_11_B():
    """
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=jp
    """
    n = ii()
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    d = [-1] * n
    f = [-1] * n
    time = 0

    def dfs(G, v):
        nonlocal time
        time += 1
        d[v] = time
        for nv in G[v]:
            if d[nv] != -1:
                continue
            dfs(G, nv)
        time += 1
        f[v] = time

    for v in range(n):
        if d[v] != -1:
            continue
        dfs(g, v)
    for i in range(n):
        print(i + 1, d[i], f[i])
# verified on 2019/07/02


def AOJ_ALDS_1_11_C():
    """
    各頂点の0からの最短距離を bfs で求める
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
    """
    q = Queue()
    n = ii()
    dist = [-1 for _ in range(n)]
    g = Graph(n)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1)
    q.put(0)
    dist[0] = 0
    while not q.empty():
        v = q.get()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                q.put(nv)
    for i in range(n):
        print(i + 1, dist[i])
# verified on 2019/07/02


def AOJ_GRL_1_A():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"""
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    for i in g.dijkstra(start):
        if i == float('inf'):
            print('INF')
        else:
            print(i)
    # debug(g)
# verified on 2019/07/02


def AOJ_ALDS_1_11_C_kai():
    """
    各頂点の0からの最短距離を dijkstra で求める。
    http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
    """
    n = ii()
    g = Graph(n, Weighted=True)
    for i in range(n):
        u, k, *v = mi()
        for j in v:
            g.add_edge(u - 1, j - 1, 1)
    dist = g.dijkstra(0)
    for i in range(n):
        if dist[i] == float('inf'):
            print(i + 1, -1)
        else:
            print(i + 1, dist[i])
# verified on 2019/07/02


def AOJ_GRL_1_B():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp"""
    n, m, start = mi()
    g = Graph(n, Weighted=True, Directed=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.bellman_ford(start)
    if d == False:
        print("NEGATIVE CYCLE")
    else:
        d = list(map(lambda x: x if x != float('inf') else 'INF', d))
        for i in d:
            print(i)
# verified on 2019/07/02


def AOJ_GRL_1_C():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C&lang=jp"""
    n, m = mi()
    g = Graph(n, Weighted=True, Directed=True, Matrix=True)
    for i in range(m):
        s, t, w = mi()
        g.add_edge(s, t, w)
    d = g.warshall_froyd()
    d = [list(map(lambda x: x if x != float('inf') else 'INF', d[i]))
         for i in range(n)]
    for i in range(n):
        if d[i][i] < 0:
            print('NEGATIVE CYCLE')
            sys.exit()
    for i in d:
        print(*i)
# verified on 2019/07/02


def ABC132_E():
    """
    頂点3倍するdijkstra法。頂点倍加の典型例として
    https://atcoder.jp/contests/abc132/tasks/abc132_e
    """
    N, M = mi()
    g = Graph(3 * N)
    for i in range(M):
        a, b = mi()
        g.add_edge(a - 1, b + N - 1)
        g.add_edge(a + N - 1, b + 2 * N - 1)
        g.add_edge(a + 2 * N - 1, b - 1)
    S, T = mi()
    ans = g.dijkstra(S - 1)[T - 1]
    if ans == float('inf'):
        print(-1)
    else:
        print(ans // 3)


def ABC079_D():
    """https://atcoder.jp/contests/abc079/tasks/abc079_d"""
    H, W = mi()
    mat = [[] for __ in range(10)]
    for i in range(10):
        mat[i] = lmi()
    g = Graph(10, Matrix=True, Weighted=True)
    g.graph = mat
    cost = g.warshall_froyd()
    field = [[] for _ in range(H)]
    for i in range(H):
        field[i] = lmi()
    ans = 0
    for i in range(H):
        for j in range(W):
            if field[i][j] != -1:
                ans += cost[field[i][j]][1]
    print(ans)


if __name__ == '__main__':
    # AOJ_ALDS_1_11_A()
    # AOJ_ALDS_1_11_B()
    # AOJ_ALDS_1_11_C()
    # AOJ_GRL_1_A()
    # AOJ_ALDS_1_11_C_kai()
    # AOJ_GRL_1_B()
    # AOJ_GRL_1_C()
    ABC132_E()
    # ABC079_D()

Submission status: Runtime Error

Solution code:
from collections import*
n, m, *t = map(int, open().read().split())       
*w, s, t = [a-1for a in t]         
e = [[]for _ in range(n)]        
for u, v in zip(w[::2], w[1::2]):      
    e[u].append(v)

INF = 10**10
f = [[INF]*3for _ in range(n)]        
f[s][0] = 0        
q = deque([(s, 0)])           
while q:
    vi, j = q.popleft()         
    if vi == t and j == 0:
        print(f[vi][0]//3)
        break
    for ui in e[vi]:           
        if f[ui][(j+1)%3] < INF: continue           
        f[ui][(j+1)%3] = f[vi][j] + 1
        q.append((ui, (j+1)%3))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import*
n, m, *t = map(int, open("test").read().split())       
*w, s, t = [a-1for a in t]         
e = [[]for _ in range(n)]        
for u, v in zip(w[::2], w[1::2]):      
    e[u].append(v)

INF = 10**10
f = [[INF]*3for _ in range(n)]        
f[s][0] = 0        
q = deque([(s, 0)])           
while q:
    vi, j = q.popleft()         
    if vi == t and j == 0:
        print(f[vi][0]//3)
        break
    for ui in e[vi]:           
        if f[ui][(j+1)%3] < INF: continue           
        f[ui][(j+1)%3] = f[vi][j] + 1
        q.append((ui, (j+1)%3))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(m):
    u,v=map(int,input().split())
    branch[u-1]|={v-1}
s,t=map(int,input().split())
s-=1
t-=1
dist=[[float('inf')]*3 for i in range(n)]
check={(s,0)}
dist[s][0]=0
while len(check)>0:
    now,nowd=check.pop()
    for nex in branch[now]:
        if dist[nex][(nowd+1)%3]>dist[now][nowd]+1:
            ans[nex][(nowd+1)%3]=ans[now][nowd]+1
            check|={(nex,(nowd+1)%3)}
if dist[t][0]>10**18:
    print(-1)
else:
    print(dist[t][0]//3)

Submission status: Runtime Error

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
    rireki = rireki | after
    after = after - rireki
if flag == 1:
    print(-1)
if flag == 2:
    print(counter)

Submission status: Runtime Error

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

########

if __name__ == "__main__":
    N, M = l_inpl()

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

    for _ in range(M):
        u, v = l_inpl()
        u, v = u-1, v-1
        to[u].append(v)

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

    dist = [[INF, INF, INF] for _ in range(N)]
    dist[S][0] = 0

    q = deque([S, 0])

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

Submission status: Runtime Error

Solution code:
from collections import deque

class unionFind:
    par = []
    def __init__(self, N):
        self.par = [i for i in range(N+1)]
    
    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        else:
            self.par[rx] = ry

    def same(self, x, y):
        return self.root(x) == self.root(y)

N, M = map(int, input().split())
uf = unionFind(3*N)
g = {i: [] for i in range(3*N + 1)}


for i in range(M):
    e = list(map(int, input().split()))
    g[3*e[0]].append(3*e[1] - 1)
    g[3*e[0] - 1].append(3*e[1] - 2)
    g[3*e[0] - 2].append(3*e[1])
    uf.unite(3*e[0], 3*e[1]-1)
    uf.unite(3*e[0]-1, 3*e[1]-2)
    uf.unite(3*e[0]-2, 3*e[1])
    

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

if not uf.same(S*3, T*3):
    print(-1)
else:
    q = deque([])
    qset = set()
    fp = []
    # root
    q.append((3*S, 0))
    qset.add(3*S)
    while len(q) > 0:
        now = q.popleft()
        for node in g[now[0]]:
            if node == 3*T:
                print((now[1]+1)//3)
                q.clear()
                break
            if node not in fp and node not in qset:
                q.append((node, now[1]+1))
                qset.add(node)
        fp.append(now[0])

Submission status: Runtime Error

Solution code:
from collections import deque

class unionFind:
    par = []
    def __init__(self, N):
        self.par = [i for i in range(N+1)]
    
    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        else:
            self.par[rx] = ry

    def same(self, x, y):
        return self.root(x) == self.root(y)

N, M = map(int, input().split())
uf = unionFind(3*N)
g = {i: [] for i in range(3*N + 1)}


for i in range(M):
    e = list(map(int, input().split()))
    g[3*e[0]].append(3*e[1] - 1)
    g[3*e[0] - 1].append(3*e[1] - 2)
    g[3*e[0] - 2].append(3*e[1])
    uf.unite(3*e[0], 3*e[1]-1)
    uf.unite(3*e[0]-1, 3*e[1]-2)
    uf.unite(3*e[0]-2, 3*e[1])

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

if not uf.same(S*3, T*3):
    print(-1)
else:
    q = deque([])
    qset = set()
    fp = []
    # root
    q.append((3*S, 0))
    qset.add(3*S)
    while len(q) > 0:
        now = q.popleft()
        for node in g[now[0]]:
            if node == 3*T:
                print((now[1]+1)//3)
                q.clear()
                break
            if node not in fp and node not in qset:
                q.append((node, now[1]+1))
                qset.add(node)
        fp.append(now[0])

Submission status: Runtime Error

Solution code:
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)

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

Submission status: Runtime Error

Solution code:
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(M)]
for u, v in UV:
	graph[u - 1] += [v - 1]

INF = 10 ** 12
cost = [[INF, INF, INF] for _ in range(M)]
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, 0, 0)

print(cost[T - 1][0] // 3 if 0 == cost[T - 1][0] % 3 else -1)

Submission status: Runtime Error

Solution code:
N,M= map(int,input().split())
uv = [0]*M
for i in range(M):
    uv[i]=list(map(int, input().split()))
S,T= map(int,input().split())

# ans = [10**5]
graph = [[] for j in range(N)]
for i in range(M):
    graph[uv[i][0]-1].append([uv[i][0]-1,uv[i][1]-1])



#graphにはインデックス

next_stack = []
visit = [[0 for i in range(3)] for j in range(N)]
trace_count = 0
now_pos = [S-1,0]
ans = [10**5]
nextu = 0
visit[now_pos[0]][now_pos[1]]+=1
# print(visit)

#拡張BFS
def bfs(now_pos,visit,trace_count,ans,next_stack):
    # print(now_pos)
    # visit[now_pos[0]][now_pos[1]] += 1
    if visit[now_pos[0]][now_pos[1]]>=2:
        return
    if now_pos == [T-1,0]:
        # print("aa")
        if ans[0] > trace_count//3:
            ans[0] = trace_count//3
    #現在のノードからいけるノードを追加する
    if now_pos[1]==2:
        nextu = 0
    else:
        nextu = now_pos[1]+1

    
    # print(graph[now_pos[0]])
    for node in graph[now_pos[0]]:
        # print(node)
        next_stack.append([node[1],nextu])

    if len(next_stack)==0:
        return


    while(len(next_stack)!=0):
        node = next_stack.pop()
        visit[node[0]][node[1]]+=1
        bfs(node,visit,trace_count+1,ans,next_stack)
        visit[node[0]][node[1]]-=1


    return



bfs(now_pos,visit,trace_count,ans,next_stack)

if ans[0] == 10**5:
    ans[0] = -1


print(ans[0])

Submission status: Runtime Error

Solution code:
N,M= map(int,input().split())
uv = [0]*M
for i in range(M):
    uv[i]=list(map(int, input().split()))
S,T= map(int,input().split())

# ans = [10**5]
graph = [[] for j in range(N)]
for i in range(M):
    graph[uv[i][0]-1].append([uv[i][0]-1,uv[i][1]-1])



#graphにはインデックス

next_stack = []
visit = [[0 for i in range(3)] for j in range(N)]
trace_count = 0
now_pos = [S-1,0]
ans = [10**5]
nextu = 0
visit[now_pos[0]][now_pos[1]]+=1
# print(visit)

#拡張BFS
def bfs(now_pos,visit,trace_count,ans,next_stack):
    # print(now_pos)
    # visit[now_pos[0]][now_pos[1]] += 1
    if visit[now_pos[0]][now_pos[1]]>=2:
        return
    if now_pos == [T-1,0]:
        # print("aa")
        if ans[0] > trace_count//3:
            ans[0] = trace_count//3
    #現在のノードからいけるノードを追加する
    if now_pos[1]==2:
        nextu = 0
    else:
        nextu = now_pos[1]+1

    
    # print(graph[now_pos[0]])
    for node in graph[now_pos[0]]:
        # print(node)
        next_stack.append([node[1],nextu])

    if len(next_stack)==0:
        return


    while(next_stack):
        node = next_stack.pop()
        visit[node[0]][node[1]]+=1
        bfs(node,visit,trace_count+1,ans,next_stack)
        visit[node[0]][node[1]]-=1


    return



bfs(now_pos,visit,trace_count,ans,next_stack)

if ans[0] == 10**5:
    ans[0] = -1


print(ans[0])

Submission status: Runtime Error

Solution code:
N,M= map(int,input().split())
uv = [0]*M
for i in range(M):
    uv[i]=list(map(int, input().split()))
S,T= map(int,input().split())

# ans = [10**5]
graph = [[] for j in range(N)]
for i in range(M):
    graph[uv[i][0]-1].append([uv[i][0]-1,uv[i][1]-1])



#graphにはインデックス

next_stack = []
visit = [[0 for i in range(3)] for j in range(N)]
candidate = []
trace_count = 0
now_pos = [S-1,0]
ans = [10**5]
nextu = 0
visit[now_pos[0]][now_pos[1]]+=1
# print(visit)

#拡張BFS
def bfs(now_pos,visit,trace_count,ans,next_stack):
    # print(now_pos)
    # visit[now_pos[0]][now_pos[1]] += 1
    if visit[now_pos[0]][now_pos[1]]>=2:
        return
    if now_pos == [T-1,0]:
        # print("aa")
        if ans[0] > trace_count//3:
            ans[0] = trace_count//3
    #現在のノードからいけるノードを追加する
    if now_pos[1]==2:
        nextu = 0
    else:
        nextu = now_pos[1]+1

    
    # print(graph[now_pos[0]])
    for node in graph[now_pos[0]]:
        # print(node)
        next_stack.append([node[1],nextu])

    if len(next_stack)==0:
        return


    while(next_stack):
        node = next_stack.pop()
        visit[node[0]][node[1]]+=1
        bfs(node,visit,trace_count+1,ans,next_stack)
        visit[node[0]][node[1]]-=1


    return



bfs(now_pos,visit,trace_count,ans,next_stack)

if ans[0] == 10**5:
    ans[0] = -1


print(ans[0])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Jul  1 11:43:19 2019

@author: Yamazaki Kenichi
"""
from collections import deque

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

Ta = [[] for i in range(3*N+1)]
for c in uv:
    Ta[c[0]].append(c[1]+N)
    Ta[c[0]+N].append(c[1]+2*N)
    Ta[c[0]+2*N].append(c[1])
del c

check = [0 for i in range(3*N+1)]

q = deque([S])
check[S] = 1
counta = 0
while len(q) > 0:
    for i in range(len(q)):
        nexts = Ta[q.popleft()]
        for next_ in nexts:
            if check[next_] != 1:
                q.append(next_)
                check[next_] = 1
    counta += 1
    if check[T] == 1:
        break

print(counta//3)

Submission status: Runtime Error

Solution code:
def step(u,k,t):
    if t==3:
        t=0
        for v in l[u]:
            if ans[v]>k//3:
                ans[v]=k//3
                step(v,k+1,t+1)
    else:
        for v in l[u]:
            step(v,k+1,t+1)

import sys
sys.setrecursionlimit(200000)

n,m=map(int,input().split())
l=[[] for z in range(n+1) ]
for _ in range(m):
    u,v=map(int,input().split())
    l[u].append(v)
s,t=map(int,input().split())
ans=[100000 for x in range(n+1)]
step(s,1,1)
#print(ans)
if ans[t]==100000:
    print("-1")
else:
    print(ans[t])

Submission status: Runtime Error

Solution code:
def dfs():
  while len(q) > 0:
  	p = q.pop()
  	for e in g[p]:
      if d[e] < 0 or d[e] > d[p] + 1:
        d[e] = d[p] + 1
        q.append(e)
  
  
n, m = map(int, input().split())
g = [[] for i in range(3 * (n+1))]
for i in range(m):
  u, v = map(int, input().split())
  g[3*u].append(3*v+1)
  g[3*u+1].append(3*v+2)
  g[3*u+2].append(3*v)

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

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
import heapq
import sys

N, M = map(int, input().split())
MAX = math.inf

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

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

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

# init
d = [
    [math.inf for i in range(N)],
    [math.inf for i in range(N)],
    [math.inf for i in range(N)],
]
d[0][S] = 0
queue = []
heapq.heappush(queue, [0, 0, S])

while queue:
    p, m, n = heapq.heappop(queue)
    if m == 0 and n == T:
        print(int(p/3))
        sys.exit(0)
    for to in nodes[n]:
        if d[(m+1) % 3][to] > d[m][n] + 1:
            d[(m+1) % 3][to] = d[m][n] + 1
            heapq.heappush(queue, [
                d[(m+1) % 3][to],
                (m+1) % 3,
                to
            ])

print(-1)
sys.exit(0)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
import heapq

N, M = map(int, input().split())
MAX = math.inf

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

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

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

# init
d = [
    [math.inf for i in range(N)],
    [math.inf for i in range(N)],
    [math.inf for i in range(N)]
]
d[0][S] = 0
queue = []
heapq.heappush(queue, [0, 0, S])

while queue:
    p, m, n = heapq.heappop(queue)
    if m == 0 and n == T:
        print(int(p/3))
        quit()
    for to in nodes[n]:
        if d[(m+1) % 3][to] > d[m][n] + 1:
            d[(m+1) % 3][to] = d[m][n] + 1
            heapq.heappush(queue, [
                d[(m+1) % 3][to],
                (m+1) % 3,
                to
            ])

print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
import heapq

N, M = map(int, input().split())
MAX = math.inf

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

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

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

# init
d = [
    [math.inf for i in range(N)],
    [math.inf for i in range(N)],
    [math.inf for i in range(N)],
]
d[0][S] = 0
queue = []
heapq.heappush(queue, [0, 0, S])

while queue:
    p, m, n = heapq.heappop(queue)
    if m == 0 and n == T:
        print(int(p/3))
        quit()
    for to in nodes[n]:
        if d[(m+1) % 3][to] > d[m][n] + 1:
            d[(m+1) % 3][to] = d[m][n] + 1
            heapq.heappush(queue, [
                d[(m+1) % 3][to],
                (m+1) % 3,
                to
            ])

print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np


N, M = map(int, input().split())
conn = np.zeros((N + 1, N + 1), dtype=bool)
for _ in range(M):
    u, v = map(int, input().split())
    conn[u, v] = 1
S, T = map(int, input().split())


def hop3(n1):
    n2 = np.dot(n1, conn)
    n3 = np.dot(n2, conn)
    return np.dot(n3, conn)


ans = 1
n = np.zeros((1, N + 1), dtype=bool)
n[0, S] = 1

while True:
    m = hop3(n)
    if (n == m).all():
        break
    if m[0, T] != 0:
        print(ans)
        exit()
    ans += 1
    n = m
print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from scipy.special 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)