[BOJ] #16928：蛇与梯子游戏（Python）

import sys
from collections import deque
 
N, M = list(map(int, sys.stdin.readline().split()))
arr = [99] * 101 # 1부터 100까지의 칸을 저장하는 배열, 기본값은 99로 설정
snakes = {} # 사다리와 뱀의 위치를 저장하는 딕셔너리
 
for _ in range(N + M):
  a, b = list(map(int, sys.stdin.readline().split()))
  snakes[a] = b # 사다리와 뱀의 시작 위치를 key로, 끝 위치를 value로 저장
 
arr[1] = 0
dq = deque([1]) # 큐에 1번 칸을 추가
 
while dq:
  x = dq.pop() # 큐에서 꺼낸 칸
  for i in range(1, 7): # 1부터 6까지의 주사위를 굴려서 이동할 수 있는 칸을 확인
    if x + i > 100: # 100번 칸을 넘어가면 무시
      continue
    elif x + i in snakes.keys(): # 사다리와 뱀의 위치를 확인
      if arr[x] + 1 < arr[snakes[x+i]]: # 값이 업데이트되는 경우
        arr[snakes[x+i]] = arr[x] + 1
        dq.append(snakes[x+i]) # 업데이트된 칸을 큐에 추가
    else: # 사다리와 뱀의 위치가 아닌 경우
      if arr[x] + 1 < arr[x + i]: # 값이 업데이트되는 경우
        arr[x + i] = arr[x] + 1
        dq.append(x + i) # 업데이트된 칸을 큐에 추가
 
print(arr[-1]) # 마지막 칸(100번 칸)의 주사위 굴리기 횟수를 출력

2 1
2 60
21 99
61 20

1 5
2 99
3 2
4 2
5 2
6 2
7 2

0 0

1 5
2 92
94 3
95 4
96 5
97 6
98 7

1 1
13 99
8 7