Snakes and Ladders Game

Cubelover, who enjoys playing Snakes and Ladders, became curious one day.

If I can rig the die so that any number I want comes up, what is the fewest number of rolls needed to reach the goal?

The game uses a cube-shaped die, and each face has one of the numbers 1 through 6 written on it. The game is played on a board measuring 10×10 and divided into 100 squares in total. The board has the numbers 1 through 100 written in order, one per square.

The player must move by the number that comes up on the die. For example, if the player is on square i and rolls a 4, the player must move to square i+4. If the roll would take the player past square 100, the move is not allowed. If the square the player lands on has a ladder, the player climbs up the ladder. If the player lands on a square with a snake, the player goes down along the snake. That is, the number of a square reached by a ladder is larger than the number of the square the player was on, and the number of a square reached by a snake is smaller.

The goal of the game is to start on square 1 and reach square 100.

Given the state of the board, find the minimum number of times the die must be rolled to reach square 100.

The first line gives the number of ladders N (1 ≤ N ≤ 15) and the number of snakes M (1 ≤ M ≤ 15) on the board.

Each of the next N lines gives x, y (x < y), describing a ladder. Landing on square x moves the player to square y.

Each of the next M lines gives u, v (u > v), describing a snake. Landing on square u moves the player to square v.

Square 1 and square 100 are not the start or the end of any snake or ladder. Every square has at most one ladder or snake, and no square has both at the same time. Only inputs from which square 100 can always be reached are given.

Print the minimum number of times the die must be rolled to reach square 100.