[이코테] CH09 최단경로 실전문제 2번 미래도시

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
import copy
import itertools
from itertools import combinations
from itertools import permutations
INF = 1e9

N,M = map(int,sys.stdin.readline().split())
graph = [[INF] *(N+1) for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,sys.stdin.readline().split())
    graph[a][b] = 1 
    graph[b][a] = 1 # 양방향 가능하므로 ab,ba 모두 해줘야한다
for i in range(1,N+1):
    for j in range(1,N+1):
        if i == j:
            graph[i][j] = 0
X,K = map(int,sys.stdin.readline().split())
for k in range(1,N+1):
    for a in range(1,N+1):
        for b in range(1,N+1):
            graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])

if graph[1][X] == INF:
    print(-1)
else:
    print(graph[1][K]+graph[K][X]) # 1->K->X