Markov takes out his Snakes and Ladders game, stares at the board and wonders: "If I can always roll the die to whatever number I want, what would be the least number of rolls to reach the destination?"
The game is played with a cubic die of faces numbered to .
Starting from square , land on square with the exact roll of the die. If moving the number rolled would place the player beyond square , no move is made.
If a player lands at the base of a ladder, the player must climb the ladder. Ladders go up only.
If a player lands at the mouth of a snake, the player must go down the snake and come out through the tail. Snakes go down only.
The first line contains the number of tests, .
For each testcase:
- The first line contains , the number of ladders.
- Each of the next lines contains two space-separated integers, the start and end of a ladder.
- The next line contains the integer , the number of snakes.
- Each of the next lines contains two space-separated integers, the start and end of a snake.
The board is always with squares numbered to .
Neither square nor square will be the starting point of a ladder or snake.
A square will have at most one endpoint from either a snake or a ladder.
For each of the t test cases, print the least number of rolls to move from start to finish on a separate line. If there is no solution, print -1.