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 math import ceil
from collections import defaultdict
import heapq


class Dijkstra:
    """
    dijkstraの最短経路問題を解く
    input:
        S: start node
        mat : mat[a][b] = edge_weight(a,b)
    """

    def __init__(self, start, num_node, mat):
        """
        mat: mat[a][b] = edge_weight(a,b)
        num_node: num of nodes
        dist: dist from start_node
        prev: 最短経路において、一つ前のノードを記憶。経路復元に使う?
        """
        self.start_node = start
        self.mat = mat
        self.num_node = num_node
        self.dist = [float('inf')]*num_node
        self.prev = defaultdict(lambda: None)

        # dist form S to S = 0
        self.dist[start] = 0

    def calc_dist(self):
        """
        最短経路 distを計算する
        Q: content (dist_from_start,node)
        Qはheapqとして使う。dist_from_startの小さい順になる
        """
        Q = []
        heapq.heappush(Q, (0, self.start_node))
        while Q:
            dist_to_node, node = heapq.heappop(Q)
            # 現在の値よりも大きくて、更新にならない場合
            if self.dist[node] < dist_to_node:
                continue

            # 次のホップを計算する
            for nex in range(self.num_node):
                weight = self.mat[node][nex]
                cand = dist_to_node + weight

                if self.dist[nex] > cand:  # update
                    self.dist[nex] = cand
                    self.prev[nex] = node
                    heapq.heappush(Q, (cand, nex))

    def get_dist(self, d):
        """
            startからdまでの距離を返す
            これの前にcalc()を実行しておく
            たどり着けない場合は、float('inf')がかえる
        """
        return self.dist[d]

N,M = map(int,input().split())
grid=[[float("inf")]*N for _ in range(N)]
for _ in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    grid[a][b]=1
    grid[b][a]=1

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

D = Dijkstra(S,N,grid)
D.calc_dist()

dist = D.get_dist(T)
if dist==float("inf"):
    print(-1)
elif dist %3==0:
    print(dist//3)
elif dist%3==1:
    print((dist+1)//3+2)
elif dist%3==2:
    print((dist+1)//3+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
N,M= map(int,input().split())
g = defaultdict(list)

for i in range(M):
    u,v = list(map(int,input().split()))
    g[u].append(N + v)
    g[N + u].append(2 * N + v)
    g[2*N + u].append(v)
S,T= map(int,input().split())

dq = deque([S])
inf = 10**15
d = [inf for i in range(3*N+1)]
d[S] = 0

while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[nv] > d[v] + 1:
            d[nv] = d[v] + 1
            dq.append(nv)

if inf == d[T+2*N]:
    print(-1)
else:
    print(d[T+2*N])

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
INF = 10**18
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
s,t = map(int,input().split())

def dijkstra_heap(s,g,p):
    d = [[INF] * p for i in range(n)] 
    used = [[True] * p for i in range(n)] 
    used[s][0] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,[1,es,1]) # 回数、向かう頂点、あまり
    while len(ed_list):
        ken,v,md = heapq.heappop(ed_list)
        if not used[v][md]:
            continue
        d[v][md] = ken
        used[v][md] = False
        if not used[g][0]:
            break
        for e in edge[v]:
            if used[e][(md+1)%p]:
              if (md+1)%p == 1:
                heapq.heappush(ed_list,[ken+1,e,1])
              else:
                heapq.heappush(ed_list,[ken,e,(md+1)%p])
    return d[g][0]

ans = dijkstra_heap(s-1,t-1,3)
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
INF = 10**18
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
s,t = map(int,input().split())

def dijkstra_heap(s,g,p):
    d = [[INF] * p for i in range(n)] 
    used = [[True] * p for i in range(n)] 
    used[s][0] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,[1,es,1]) # 回数、向かう頂点、あまり
    while len(ed_list):
        ken,v,md = heapq.heappop(ed_list)
        if not used[v][md]:
            continue
        d[v][md] = ken
        used[v][md] = False
        if not used[g][0]:
            break
        for e in edge[v]:
            if used[e][(md+1)%p]:
              if (md+1)%p == 0:
                heapq.heappush(ed_list,[ken+1,e,0])
              else:
                heapq.heappush(ed_list,[ken,e,md+1])
    return d[g][0]

ans = dijkstra_heap(s-1,t-1,3)
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
INF = 10**18
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
s,t = map(int,input().split())

def dijkstra_heap(s,g,p):
    d = [[INF] * p for i in range(n)] 
    used = [[True] * p for i in range(n)] 
    used[s][0] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,[1,es,1]) # 回数、向かう頂点、あまり
    while len(ed_list):
        ken,v,md = heapq.heappop(ed_list)
        if not used[v][md]:
            continue
        d[v][md] = ken
        used[v][md] = False
        if not used[g][0]:
            break
        for e in edge[v]:
            if used[e][(md+1)%p]:
              if (md+1)%p == 0:
                heapq.heappush(ed_list,[ken+1,e,0])
              else:
                heapq.heappush(ed_list,[ken,e,md+1])
    return d[n-1][0]

ans = dijkstra_heap(s-1,t-1,3)
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
INF = 10**10
edge = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
s,t = map(int,input().split())

def dijkstra_heap(s,g,p):
    d = [[INF] * p for i in range(n)] 
    used = [[True] * p for i in range(n)] 
    used[s][0] = False
    ed_list = []
    for es in edge[s]:
        heapq.heappush(ed_list,[1,es,1]) # 回数、向かう頂点、あまり
    while len(ed_list):
        ken,v,md = heapq.heappop(ed_list)
        if not used[v][md]:
            continue
        d[v][md] = ken
        used[v][md] = False
        if not used[g][0]:
            break
        for e in edge[v]:
            if used[e][(md+1)%p]:
              if (md+1)%p == 0:
                heapq.heappush(ed_list,[ken+1,e,0])
              else:
                heapq.heappush(ed_list,[ken,e,md+1])
    return d[n-1][0]

ans = dijkstra_heap(s-1,t-1,3)
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

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

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

S, T = map(int, input().split())
S -= 1; T -= 1
dist = [-1] * (3*N)
dist[3*S] = 0
d = deque([[S, -1]])
while d:
  node, par = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append([child, node])

if dist[3*T] > 0:
  print(dist[3*T] // 3)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys #追加
sys.setrecursionlimit(500*500) #追加
n,m=map(int,input().split())
edge = [[] for i in range(n*3)]
#edge[i] : iから出る道の[行先]の配列
for i in range(m):
    x,y = map(int,input().split())
    x-=1;y-=1
    x*=3;y*=3
    edge[x  ].append(y+1)
    edge[x+1].append(y+2)
    edge[x+2].append(y  )
    
def dfs(s,g,res,visited):
  visited.append(s)
  if s==g or s==g+1 or s==g+2:
    if res%3==0:
      return res//3
  
  if res>m*3:
    return float("inf")
  
  l=float("inf")
  for i in edge[s]:
    if i not in visited:
      l=min(l,dfs(i,g,res+1,visited))
  return l
s,t=map(int,input().split())
s-=1;t-=1
ans=dfs(s*3,t*3,0,[])
if ans==float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from queue import PriorityQueue

N, M = map(int, input().split())

d1 = [set() for _ in range(N+1)]
d2 = [set() for _ in range(N+1)]
d3 = [set() for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    d1[u].add(v)

for i in range(1, N+1):
    for j in d1[i]:
        d2[i] = d2[i].union(d1[j])

for i in range(1, N+1):
    for j in d1[i]:
        d3[i] = d3[i].union(d2[j])

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


class UnionFind:

    def __init__(self, N: int):
        # d[i] = <parent id> if i is a child,
        #       - <size of the group> if i is a root
        self.d = [-1 for _ in range(N)]

    def root(self, x: int) -> int:
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x: int, y: int) -> bool:
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

    def size(self, x: int):
        return -self.d[self.root(x)]

    def show(self):
        m = {}
        for n in range(len(self.d)):
            r = self.root(n)

            if r not in m:
                m[r] = [n]
            else:
                m[r].append(n)

        print("root -> childs")
        print("---------------------")
        for key in m:
            print("{} -> {}".format(key, m[key]))


class Pair:
    def __init__(self, v: int, dist: int):
        self.v = v
        self.dist = dist

    def __lt__(self, other):
        return self.dist < other.dist


uf = UnionFind(N+1)

for i in range(1, N+1):
    for j in d3[i]:
        uf.unite(i, j)

if not uf.same(S, T):
    print(-1)
    exit()

# Dijkstra method
que = PriorityQueue()
que.put(Pair(S, 0))
INF = 10**9
d = [INF]*(N+1)

d[S] = 0

while(not que.empty()):
    p = que.get()
    if (d[p.v] < p.dist):
        continue
    for e in d3[p.v]:
        if d[e] > d[p.v] + 1:
            d[e] = d[p.v] + 1
            que.put(Pair(e, d[e]))

print(d[T])

Submission status: Wrong Answer

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

def MI():return map(int,input().split())
def LI():return list(MI())

from collections import deque
n,m=MI()
G=[[] for i in range(n)]
# print(G)
for i in range(m):
    u,v=MI()
    G[u-1].append(v-1)

    
s,t=MI()
s=s-1
t=t-1


dq=deque([])

visited=[False]*n
dq.append(s)
depth=0
for i in range(1,10**3+1):
    par_list=[]
    while dq:
        try:
            p=dq.popleft()
            if visited[p]==True:
                continue
            else:
                visited[p]=True
                par_list.append(p)
        except:
            break
    depth+=1
    #print(depth)
    #print(par_list)
    if len(par_list)==0:
      break
    for par in par_list:
        for c1 in G[par]:
            for c2 in G[c1]:
                for c3 in G[c2]:
                    if c3==t:
                        #print(par,c1,c2,c3,"yay")
                        print(depth)
                        exit()
                    if visited[c3]==False:
                        dq.append(c3)
                        visited[c3]==True
    
                    #print(par,c1,c2,c3,end=" ")
                    #print()
    #print(i,len(dq),dq)
    
print(-1)

Submission status: Wrong Answer

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

def MI():return map(int,input().split())
def LI():return list(MI())

from collections import deque
n,m=MI()
G=[[] for i in range(n)]
# print(G)
for i in range(m):
    u,v=MI()
    G[u-1].append(v-1)

    
s,t=MI()
s=s-1
t=t-1


dq=deque([])

visited=[False]*n
dq.append(2)
depth=0
for i in range(1,10**5+1):
    #print("----------")
    par_list=[]
    while dq:
        try:
            p=dq.popleft()
            if visited[p]==True:
                continue
            else:
                visited[p]=True
                par_list.append(p)
        except:
            break
    
    #print(par_list)
    for par in par_list:
        for c1 in G[par]:
            for c2 in G[c1]:
                for c3 in G[c2]:
                    if c3==t:
                        #print(par,c1,c2,c3,"yay")
                        print(depth)
                        exit()
                    if visited[c3]==False:
                        dq.append(c3)
                        visited[c3]==True
    
                    #print(par,c1,c2,c3,end=" ")
                    #print()
    #print(i,len(dq),dq)
    depth+=1
print(-1)

Submission status: Wrong Answer

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

def MI():return map(int,input().split())
def LI():return list(MI())

from collections import deque
n,m=MI()
G=[[] for i in range(n)]
# print(G)
for i in range(m):
    u,v=MI()
    G[u-1].append(v-1)

    
s,t=MI()
s=s-1
t=t-1


dq=deque([])

visited=[False]*n
dq.append(2)
depth=0
for i in range(1,10**5+1):
    #print("----------")
    par_list=[]
    while dq:
        try:
            p=dq.popleft()
            if visited[p]==True:
                continue
            else:
                visited[p]=True
                par_list.append(p)
        except:
            break
    depth+=1
    #print(par_list)
    for par in par_list:
        for c1 in G[par]:
            for c2 in G[c1]:
                for c3 in G[c2]:
                    if c3==t:
                        #print(par,c1,c2,c3,"yay")
                        print(depth)
                        exit()
                    if visited[c3]==False:
                        dq.append(c3)
                        visited[c3]==True
    
                    #print(par,c1,c2,c3,end=" ")
                    #print()
    #print(i,len(dq),dq)
print(-1)

Submission status: Wrong Answer

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

def MI():return map(int,input().split())
def LI():return list(MI())

from collections import deque
n,m=MI()
G=[[] for i in range(n)]
# print(G)
for i in range(m):
    u,v=MI()
    G[u-1].append(v-1)
# print(G)
    
s,t=MI()

dq=deque([])

visited=[False]*n
dq.append(s-1)

for i in range(1,10**5+1):
    # print("----------")
    try:
        par=dq.pop()
        if visited[par]==True:
            continue
        else:
            visited[par]=True
    except:
        break
    for c1 in G[par]:
        for c2 in G[c1]:
            for c3 in G[c2]:
                if c3==t-1:
                    # print(par,c1,c2,c3,"yay")
                    print(i)
                    exit()
                if visited[c3]==False:
                    dq.append(c3)
                    visited[c3]==True

                # print(par,c1,c2,c3,end=" ")
                # print()
    # print(dq)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    if m == 0:
        print(-1)
        exit()
    tmd = collections.defaultdict(list)
    for i in range(n):
        tma, tmb = list(map(int, readline().split()))
        tmd[tma-1] += [tmb-1]

    s, t = list(map(int, readline().split()))
    ql = [[-1, s-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[s-1].append(-1)
    while len(ql):
        cost, tmp = ql.popleft()
        if tmp == t - 1 and cost % 3 == 2:
            print((cost + 1) // 3)
            exit()
        else:
            for tmv in tmd[tmp]:
                if (cost + 1) % 3 not in fq[tmv]:
                    ql.append([cost + 1, tmv])
                    fq[tmv].append((cost + 1) % 3)
    print(-1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    if m == 0:
        print(-1)
        exit()
    tmd = collections.defaultdict(list)
    for i in range(n):
        tma, tmb = list(map(int, readline().split()))
        tmd[tma-1] += [tmb-1]

    s, t = list(map(int, readline().split()))
    ql = [[0, s-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[s-1].append(0)
    while len(ql):
        cost, tmp = ql.popleft()
        if tmp == t - 1 and cost % 3 == 2:
            print(cost // 3)
            exit()
        else:
            for tmv in tmd[tmp]:
                if (cost + 1) % 3 not in fq[tmv]:
                    ql.append([cost + 1, tmv])
                    fq[tmv].append((cost + 1) % 3)
    print(-1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    if m == 0:
        print(-1)
        exit()
    tmd = collections.defaultdict(list)
    for i in range(n):
        tma, tmb = list(map(int, readline().split()))
        tmd[tma-1] += [tmb-1]

    s, t = list(map(int, readline().split()))
    ql = [[0, s-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[s-1].append(0)
    while len(ql):
        cost, tmp = ql.popleft()
        if tmp == t - 1 and cost % 3 == 2:
            print(cost)
            exit()
        else:
            for tmv in tmd[tmp]:
                if (cost + 1) % 3 not in fq[tmv]:
                    ql.append([cost + 1, tmv])
                    fq[tmv].append((cost + 1) % 3)
    print(-1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    if m == 0:
        print(-1)
        exit()
    tmd = collections.defaultdict(list)
    for i in range(n):
        tma, tmb = list(map(int, readline().split()))
        tmd[tma-1] += [tmb-1]

    s, t = list(map(int, readline().split()))
    ql = [[0, s-1]]
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    fq[s-1].append(0)
    while len(ql):
        cost, tmp = ql.popleft()
        if tmp == t - 1 and cost == 2:
            print(cost)
            exit()
        else:
            for tmv in tmd[tmp]:
                if (cost + 1) % 3 not in fq[tmv]:
                    ql.append([cost + 1, tmv])
                    fq[tmv].append((cost + 1) % 3)
    print(-1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#ダイクストラ
#単一始点最短経路(正の辺のみ)
#s=始点 n=頂点数 edgeは隣接リスト(edge=[[[1,2],[2,4]],[[2,1]],[]])
#0-indexed
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  inf=10**20
  ans=[inf]*n
  ans[s]=0
  h=[[0,s]]
  while h:
    c,v=heappop(h)
    if ans[v]<c:continue
    for u,t in edge[v]:
      if c+t<ans[u]:
        ans[u]=c+t
        heappush(h,[c+t,u])
  return ans
n,m=map(int,input().split())
edge=[[]for _ in range(n*3)]
for _ in range(m):
	u,v=map(int,input().split())
	u-=1
	v-=1
	edge[u*3].append([v*3+1,1])
	edge[u*3+1].append([v*3+2,1])
	edge[u*3+2].append([v*3,1])
s,t=map(int,input().split())
s-=1
t-=1
dij=dijkstra(s,n*3,edge)
if dij[t*3]==10**20:print(-1)
else:print(dij[t*3]//3)

Submission status: Wrong Answer

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

N,K = map(int,input().split())
E = [[] for _ in range(N)]
MOD = 10**9+7

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

if N == 1:
	print(K)
	sys.exit()

color = [-1 for _ in range(N)]

stack = []
color[u] = 1
ans = K
for i,v in enumerate(E[u]):
	stack.append(v)
	ans *= (K-i-1)
	ans %= MOD

while stack:
	u = stack.pop()
	color[u] = 1
	length = 0
	for v in E[u]:
		if color[v] == -1:
			stack.append(v)
			length += 1
	tmp = 1
	for i in range(K-1-length,K-1):
		tmp *= i
		tmp %= MOD
	ans *= tmp
	ans %= MOD

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
# 12:55~
sys.setrecursionlimit(10**9)

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

S -= 1
T -= 1
#%%
adj_list = [[] for _ in range(N)]
for u,v in uv:
    adj_list[u-1].append(v-1)

INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][2] = 0

stack = [[S,0]]
while stack:
    v,count = stack.pop()
    nxt_v = adj_list[v]
    cnt = count%3
    for nv in nxt_v:
        if dist[nv][cnt]>(count+1)//3:
            dist[nv][cnt] = min(dist[nv][cnt],(count+1)//3)
            stack.append([nv,count+1])
            
            
if dist[T]==INF:
    ans = -1
else:
    ans = dist[T][2]
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
# 12:55~
sys.setrecursionlimit(10**9)

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

S -= 1
T -= 1
#%%
adj_list = [[] for _ in range(N)]
for u,v in uv:
    adj_list[u-1].append(v-1)

INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][2] = 0

def dfs(vartex, count):
    nxt_v = adj_list[vartex]
    cnt = count%3
    for nv in nxt_v:
        if dist[nv][cnt]>(count+1)//3:
            dist[nv][cnt] = min(dist[nv][cnt],(count+1)//3)
            dfs(nv,count+1)

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=[int(s) for s in input().split()]
edge = [set() for _ in range(3*N)]
for i in range(M):
  x,y=[int(s) for s in input().split()]
  edge[x-1].add(y-1+N)    #有向グラフなので片方でよい
  edge[x-1+N].add(y-1+2*N)
  edge[x-1+2*N].add(y-1)
S,T=[int(s) for s in input().split()]

#print(edge)

n=0
def dfs(start,goal):
  reach=deque([start])
  distance=[-1 for _ in range(N*3)]
  distance[n]=0
  while reach:
    _from=reach.popleft()
    for _to in edge[_from]:
      if not(_to in reach) and distance[_to]==-1:
        reach.append(_to)
        distance[_to]=distance[_from]+1
  return(distance[goal])
 
ans=dfs(S-1,T-1)
if ans==-1:
  print(-1)
else:
  print(ans//3)

Submission status: Wrong Answer

Solution code:
def o(): return map(int,input().split())
n,m = o()
g=[[] for i in range(n+1)]
for i in range(m):
  u,v = o()
  g[u] += [v]
s,t = o()
a = [[0,0,0] for i in range(n+1)]
a[s][0] = 1
p = [[s,1]]
ans=-1
while p:
  x,i = p.pop()
  for y in g[x]:
    if y==t and i%3==0:
      ans=i//3
      break
    if a[y][i%3]==0:
      a[y][i%3] = 1
      p = [[y,i+1]] + p
    if sum(a[y])==3:
      g[x].remove(y)
print(ans)

Submission status: Wrong Answer

Solution code:
def o(): return map(int,input().split())
n,m = o()
g=[[] for i in range(n+1)]
for i in range(m):
  u,v = o()
  g[u] += [v]
s,t = o()
a = [[-3,-3,-3] for i in range(n+1)]
a[s][0] = 0
p = [[s,1]]
while p:
  x,i = p.pop()
  for y in g[x]:
    if a[y][i%3]<0:
      a[y][i%3]=i
      p = [[y,i+1]] + p
    if all([j>0 for j in a[y]]):
      g[x].remove(y)
  if a[t][0] >= 0:
    break
print(a[t][0]//3)

Submission status: Wrong Answer

Solution code:
def o(): return map(int,input().split())
n,m = o()
g=[[] for i in range(n+1)]
for i in range(m):
  u,v = o()
  g[u] += [v]
s,t = o()
a = [[-3,-3,-3] for i in range(n+1)]
a[s][0] = 0
p = [[s,1]]
while p:
  x,i = p.pop()
  for y in g[x]:
    if a[y][i%3]<0:
      a[y][i%3]=i
      p += [[y,i+1]]
  if a[t][0] >= 0:
    break
print(a[t][0]//3)

Submission status: Wrong Answer

Solution code:
def o(): return map(int,input().split())
n,m = o()
g=[[] for i in range(n+1)]
for i in range(m):
  u,v = o()
  g[u] += [v]
s,t = o()
a = [[-3,-3,-3] for i in range(n+1)]
a[s][0] = 0
p = [[s,1]]
while p:
  x,i = p.pop()
  for y in g[x]:
    if a[y][i%3]<0:
      a[y][i%3]=i
      p += [[y,i+1]]
  if a[t][0] > 0:
    break
print(a[t][0]//3)

Submission status: Wrong Answer

Solution code:
import heapq as h
import sys

input=sys.stdin.readline

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

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

ans=[-1 for i in range(0,N)]
visit=[0 for i in range(0,N)]
ans[S-1]=0
visit[S-1]=1

q=[]
q.append(S-1)
h.heapify(q)
sub=[]
h.heapify(sub)
count=0
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if 100>=visit[p]:
                h.heappush(sub,p)
                visit[p]+=1
        if q==[]:
            count+=1
            if count%3==0:
                for j in sub:
                    if ans[j]==-1:
                        ans[j]=count//3
            q=sub
            sub=[]
            h.heapify(sub)
            break

print(ans[T-1])

Submission status: Wrong Answer

Solution code:
import heapq as h
import sys

input=sys.stdin.readline

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

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

ans=[-1 for i in range(0,N)]
visit=[0 for i in range(0,N)]
ans[S-1]=0
visit[S-1]=1

q=[]
q.append(S-1)
h.heapify(q)
sub=[]
h.heapify(sub)
count=0
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if 10>=visit[p]:
                h.heappush(sub,p)
                visit[p]+=1
        if q==[]:
            count+=1
            if count%3==0:
                for j in sub:
                    if ans[j]==-1:
                        ans[j]=count//3
            q=sub
            sub=[]
            h.heapify(sub)
            break

print(ans[T-1])

Submission status: Wrong Answer

Solution code:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n, m = list(map(int, ipti().split()))
    node_next = [set() for _ in range(n)]
    node_kenken = [set() for _ in range(n)]
    uf = UnionFind(n)

    for i in range(m):
        u, v = list(map(int, ipti().split()))
        u, v = u - 1, v - 1
        node_next[u].add(v)

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

    que = deque()

    for i in range(n):
        que.append((i, 0))
        snode = i
        while que:
            cnode, dist = que.popleft()
            if dist < 2:
                for nnode in node_next[cnode]:
                    que.append((nnode, dist + 1))
            else:
                for nnode in node_next[cnode]:
                    if snode != nnode:
                        node_kenken[snode].add(nnode)
                        uf.union(snode, nnode)

    if uf.same(s, t):
        que.append((s, 0))
        while que:
            cnode, dist = que.popleft()
            for nnode in node_kenken[cnode]:
                if nnode == t:
                    dist += 1
                    print(dist)
                    sys.exit()
                else:
                    que.append((nnode, dist + 1))

    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
mod = 10**9 + 7

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

for _ in range(m):
    u, v = [int(x) for x in input().split()]
    g[u - 1].append(v - 1)

s, t = [int(x) for x in input().split()]

g2 = [[] for _ in range(n)]

def bfs3(u):
    queue = deque([u])
    for _ in range(3):
        next_queue = deque([])
        while queue:
            v = queue.popleft()
            for i in g[v]:
                next_queue.append(i)
        queue = next_queue
    return list(set(next_queue))



for i in range(n):
    g2[i] = bfs3(i)

d = [-1]*n

def dfs(u):
    stack = [u]
    d[u] = 0
    while stack:
        v = stack.pop()
        for i in g2[v]:
            if d[i] < 0:
                d[i] = d[v] + 1
                stack.append(i)
    return d

d = dfs(s - 1)

print(d[t - 1])