Up and Down

Time limit1sMemory limit128 MB

Summary

Given ladders and chutes on a path up to 1e9 and jumps of at most s (2 to 6), find the minimum number of turns to reach space w.

Level: Medium7 of 10
Topics: BFS, Greedy, Graph
Solved: No attempts yet

Problem

This problem is based on the children's board game Chutes and Ladders (also known as Snakes and Ladders), in which players advance along a numbered path. When a player lands on the bottom of a ladder, they immediately climb to its top on the same turn; when they land on the top of a chute, they immediately slide to its bottom on the same turn. The goal is to reach the final space of the path.

In the original children's game, the number of spaces you move each turn is chosen at random, so the players make no decisions. In this version, called Up and Down, on each turn you may choose how many spaces to jump forward: any integer from $1$ to $s$ .

For example, consider a path with spaces numbered $0$ to $28$ and several chutes and ladders, where jumps of $1$ , $2$ , or $3$ are allowed. One sequence of moves reaches the last space in $5$ turns, while another reaches it in only $4$ turns; with a maximum jump of $3$ , four turns is the minimum possible for that configuration.

With more chutes and ladders and many more spaces, finding the fewest turns becomes much harder. Design your algorithm carefully, because the number of spaces can be very large (see the limits below).

Input

The input consists of one to twenty datasets, followed by a line containing a single $0$ .

The first line of a dataset contains three space-separated integers $w$ , $s$ , $p$ :

$w$ is the number of the winning space, $3 \le w \le 1{,}000{,}000{,}000$ ;
$s$ is the maximum number of spaces you may jump in one turn, $2 \le s \le 6$ ;
$p$ is the total number of chutes and ladders, $1 \le p \le 40$ .

The remaining lines of the dataset contain $p$ pairs of integers $b_i\ e_i$ (for $i = 1, 2, \dots, p$ ). Each pair means that a turn ending on space $b_i$ actually finishes on space $e_i$ (a ladder if $e_i > b_i$ , a chute if $e_i < b_i$ ). All of these $2p$ numbers are positive, strictly less than $w$ , and all distinct; the values $b_i$ are given in increasing order. Numbers on these lines are separated by a single blank or a newline. For every dataset it is guaranteed that space $w$ can be reached starting from space $0$ .

Output

For each dataset, output a single line containing the minimum number of turns needed to travel from space $0$ to space $w$ , where on each turn you jump forward by a positive integer of at most $s$ spaces, landing exactly on space $w$ without jumping past it.

Examples8

Example 1

Input

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

Expected output

4
3

Example 2
Input
```
3 2 1
1 2
0
```
Expected output
```
2
```
Example 3
Input
```
20 2 2
7 3 15 4
0
```
Expected output
```
10
```
Example 4
Input
```
100 5 1
10 90
0
```
Expected output
```
4
```

Example 5

Input

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

Expected output

3
4
2

Example 6
Input
```
60 3 3
4 20 22 40 42 58
0
```
Expected output
```
5
```
Example 7
Input
```
45 6 4
3 30 12 40 20 8 33 25
0
```
Expected output
```
3
```
Example 8
Input
```
40 3 5
2 18
5 13
12 6
17 25
20 15
0
```
Expected output
```
8
```