오르락내리락

시간 제한1초메모리 제한128 MB

요약

최대 10억 길이의 경로에 사다리와 미끄럼틀이 놓여 있고 한 번에 s(2~6)칸까지 이동할 수 있을 때, w에 도달하는 최소 턴 수를 구한다.

난이도: 보통10점 중 7점
유형: BFS, 그리디, 그래프
정답자: 아직 제출이 없습니다

문제

이 문제는 어린이 보드게임인 뱀과 사다리(사다리와 미끄럼틀) 게임을 바탕으로 한다. 이 게임에서 말은 번호가 매겨진 길을 따라 앞으로 나아간다. 말이 사다리의 아래쪽에 도착하면 같은 차례에 곧바로 사다리 위쪽으로 올라가고, 미끄럼틀의 위쪽에 도착하면 같은 차례에 곧바로 미끄럼틀 아래쪽으로 미끄러져 내려간다. 목표는 길의 마지막 칸에 도달하는 것이다.

원래의 어린이 게임에서는 한 차례에 몇 칸을 움직일지가 무작위로 정해지므로 참가자는 아무런 선택도 하지 않는다. 하지만 이 문제, 즉 오르락내리락(Up and Down) 에서는 매 차례마다 앞으로 몇 칸을 뛸지 직접 선택할 수 있다. 뛸 수 있는 칸 수는 $1$ 이상 $s$ 이하의 정수 중 하나이다.

예를 들어 $0$ 번부터 $28$ 번까지 번호가 매겨진 길에 여러 개의 사다리와 미끄럼틀이 있고, 한 차례에 $1$ , $2$ , $3$ 칸까지 뛸 수 있다고 하자. 어떤 이동 방법으로는 $5$ 번의 차례 만에 마지막 칸에 도달할 수 있고, 다른 방법으로는 단 $4$ 번의 차례 만에 도달할 수 있다. 최대 $3$ 칸까지 뛸 수 있는 이 배치에서 $4$ 가 가능한 최소 차례 수이다.

사다리와 미끄럼틀이 더 많아지고 칸의 수가 훨씬 커지면 최소 차례 수를 찾는 일이 훨씬 어려워진다. 칸의 수가 아래 제한처럼 매우 커질 수 있으므로 알고리즘을 신중하게 설계해야 한다.

입력

입력은 $1$ 개 이상 $20$ 개 이하의 데이터 집합으로 이루어지며, 마지막에는 $0$ 하나만 있는 줄이 온다.

각 데이터 집합의 첫 줄에는 공백으로 구분된 세 정수 $w$ , $s$ , $p$ 가 주어진다.

$w$ 는 도착(승리) 칸의 번호이며 $3 \le w \le 1{,}000{,}000{,}000$ 이다.
$s$ 는 한 차례에 뛸 수 있는 최대 칸 수이며 $2 \le s \le 6$ 이다.
$p$ 는 미끄럼틀과 사다리의 총 개수이며 $1 \le p \le 40$ 이다.

이어지는 줄에는 $p$ 개의 정수 쌍 $b_i\ e_i$ ( $i = 1, 2, \dots, p$ )가 주어진다. 각 쌍은 어떤 차례가 $b_i$ 번 칸에서 끝나면 실제로는 $e_i$ 번 칸에서 끝난다는 뜻이다( $e_i > b_i$ 이면 사다리, $e_i < b_i$ 이면 미끄럼틀). 이 $2p$ 개의 정수는 모두 양수이고 $w$ 보다 작으며, 모두 서로 다르다. $b_i$ 값들은 증가하는 순서로 주어진다. 이 줄들의 수는 공백 하나 또는 줄바꿈으로 구분된다. 모든 데이터 집합에서 $0$ 번 칸에서 출발하여 $w$ 번 칸에 도달하는 것이 항상 가능함이 보장된다.

출력

각 데이터 집합마다, $0$ 번 칸에서 출발하여 $w$ 번 칸에 도달하는 데 필요한 최소 차례 수를 한 줄에 출력한다. 매 차례에는 $s$ 이하의 양의 정수만큼 앞으로 뛰며, $w$ 번 칸을 지나치지 않고 정확히 그 칸에 도착해야 한다.

예제8

예제 1

입력

28 3 5
2 18 5 13 12 6
17 25 20 15
50 6 1
9 45
0

예상 출력

4
3

예제 2
입력
```
3 2 1
1 2
0
```
예상 출력
```
2
```
예제 3
입력
```
20 2 2
7 3 15 4
0
```
예상 출력
```
10
```
예제 4
입력
```
100 5 1
10 90
0
```
예상 출력
```
4
```

예제 5

입력

10 3 1
5 8
15 2 4
3 11 6 9 10 13 12 1
7 4 1
2 6
0

예상 출력

3
4
2

예제 6
입력
```
60 3 3
4 20 22 40 42 58
0
```
예상 출력
```
5
```
예제 7
입력
```
45 6 4
3 30 12 40 20 8 33 25
0
```
예상 출력
```
3
```
예제 8
입력
```
40 3 5
2 18
5 13
12 6
17 25
20 15
0
```
예상 출력
```
8
```