[이코테]미래 도시

 

 

Floyd-Warshall 알고리즘으로 노드간 최단경로 구한다

1~k까지 최단거리 + k~x까지 최단거리 구한다

 

import sys
input = sys.stdin.readline
INF = int(1e9)

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

graph=[[INF]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
  for j in range(1,n+1):
    if i==j:
      graph[i][j]=0
      
for _ in range(m):
  x,y = map(int,input().split())
  graph[x][y]=1
  graph[y][x]=1

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

for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])


if graph[1][k]==INF or graph[k][x]==INF:
  print(-1)
else:
  print(graph[1][k]+graph[k][x])