Snakes and ladders is a popular game for kids (and cute Dogs of course). Usually this game is played between multiple players but Toby does not like the other pups in his school, and wants to play alone. The game is very simple, Toby starts at position 1 of a board of height H and width W and the goal is to get to position H × W .
Each turn Toby rolls a fair die and advances a number of positions equal to the result of the die. If at the end of a turn Toby lands at the bottom of a ladder he advances immediately to the top, and if Toby lands at the head of a snake then he goes back to the tail of the snake immediately as well.
Board of the third test case sample
Remember that a fair die is a die where the probability to get any outcome between 1 and 6 is the same. In the figure 1 you can see a sample board. To explain what happens when Toby is close to the finish let’s make an example with this board. Let’s suppose that Toby is at position 29. Then Toby rolls the die, if he gets one he advances to position 30 and wins. If he gets 2, he lands in 29 again (Advance one and go one back). If he gets, 3 he lands in 28 (Advance one and go two back). If he gets 4, he lands in 27 and then immediately goes to position 1 since he stepped in the head of a snake.
Now Toby wants to know how long will it take his game before it ends, and he asks you to compute the expected amount of turns (die rolls) before he wins. It is guaranteed that it is always possible to reach the goal of the board and that the maximum expected number of turns will not exceed 100 000. The starting cell will never be the base of a ladder and the target cell will never be the head of a snake.
Input
The input consists of several test cases. Each test case begins with a line with three integers W , H and S. Here W and H are as above and S is the number of snakes or ladders. Then follow S lines, each with two integers ui and vi meaning if you land in the cell ui you have to go to cell vi immediately. So ifui
2/2 • 0 ≤ S ≤ W ×H 2 • 1 ≤ ui, vi ≤ W × H Output For each test case print a single number consisting on the expected number of turns to finish the game. The answer will be considered correct if the difference with respect to the right answer is less than 10−2. Sample Input 710 650 658 3 22 17 4 58 19 7 21 9 11 26 27 1 20 29 Sample Output 6.00000000 13.04772792 19.83332560