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?"   

Rules
The game is played with a cubic die of $\boldsymbol{6}$ faces numbered $\mbox{1}$ to $\boldsymbol{6}$.

Starting from square $\mbox{1}$, land on square $100$ with the exact roll of the die.  If moving the number rolled would place the player beyond square $100$, 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.

Function Description  

Complete the quickestWayUp function in the editor below.  It should return an integer that represents the minimum number of moves required.  

quickestWayUp has the following parameter(s):  

ladders: a 2D integer array where each $ladders[i]$ contains the start and end cell numbers of a ladder   
snakes: a 2D integer array where each $snakes[i]$ contains the start and end cell numbers of a snake  

Input Format

The first line contains the number of tests, $\boldsymbol{\boldsymbol{t}}$.   

For each testcase: 

- The first line contains $n$, the number of ladders. 

- Each of the next $n$ lines contains two space-separated integers, the start and end of a ladder. 

- The next line contains the integer $m$, the number of snakes. 

- Each of the next $m$ lines contains two space-separated integers, the start and end of a snake.

Constraints

$1\leq t\leq10$ 

$1\leq n,m\leq15$   

The board is always $10\times10$ with squares numbered  to $1$ to $100$ 

Neither square $1$ nor square $100$ 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.  

Output Format

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.

Sample Input
2
3
32 62
42 68
12 98
7
95 13
97 25
93 37
79 27
75 19
49 47
67 17
4
8 52
6 80
26 42
2 72
9
51 19
39 11
37 29
81 3
59 5
79 23
53 7
43 33
77 21 

Sample Output
3
5

Explanation

For the first test:  

The player can roll a $5$ and a $\boldsymbol{6}$ to land at square $12$.  There is a ladder to square $98$.  A roll of $2$ ends the traverse in $3$ rolls.  

For the second test:  

The player first rolls $5$ and climbs the ladder to square $80$.  Three rolls of $6$ get to square $98$.  A final roll of $2$ lands on the target square in $5$ total rolls.

Difficulty: MEDIUM
Tags: Graph algorithms

Starter code:

Solutions:
import math
t = int(input())
for _ in range(t):
	n = int(input())
	ladders = {}
	snakes = {}
	board = [0] * 100
	visited = set()
	for i in range(n):
		(start, end) = map(int, input().split())
		ladders[start - 1] = end - 1
	m = int(input())
	for i in range(m):
		(start, end) = map(int, input().split())
		snakes[start - 1] = end - 1
	for i in reversed(range(99)):
		if i in ladders:
			board[i] = board[ladders[i]] + 1
		else:
			board[i] = board[i + 1] + 1
	for i in reversed(range(99)):
		if i in snakes:
			snake_option = board[snakes[i]] + 1
			no_snake_option = board[i + 1] + 1
			if snake_option < no_snake_option:
				board[i] = snake_option
			else:
				board[i] = no_snake_option
		elif i in ladders:
			ladder_option = board[ladders[i]] + 1
			no_ladder_option = board[i + 1] + 1
			if ladder_option < no_ladder_option:
				board[i] = ladder_option
			else:
				board[i] = no_ladder_option
		else:
			board[i] = board[i + 1] + 1
	rolls = cur_pos = 0
	while cur_pos < 99:
		best_pos = cur_pos
		for i in range(6):
			next_pos = cur_pos + i + 1
			if next_pos > 99:
				break
			if board[next_pos] < board[best_pos]:
				best_pos = next_pos
		rolls += 1
		if best_pos in visited:
			rolls = -1
			break
		visited.add(best_pos)
		if best_pos in ladders:
			cur_pos = ladders[best_pos]
		elif best_pos in snakes:
			cur_pos = snakes[best_pos]
		else:
			cur_pos = best_pos
	print(rolls)


import sys

def findRoute():
	positions = oldPositions = {1}
	moves = 0
	jumps = {}
	for ladders in range(int(sys.stdin.readline())):
		ladder = sys.stdin.readline().split()
		jumps[int(ladder[0])] = int(ladder[1])
	for snakes in range(int(sys.stdin.readline())):
		snake = sys.stdin.readline().split()
		jumps[int(snake[0])] = int(snake[1])
	while endPos not in positions and moves != 100:
		moves += 1
		oldPositions = positions
		positions = set()
		for pos in oldPositions:
			for dice in range(1, 7):
				newPos = pos + dice
				positions.add(jumps.get(newPos, newPos))
	print(moves if moves != 100 else -1)
endPos = 100
for times in range(int(sys.stdin.readline())):
	findRoute()


import sys
lines = [line.strip() for line in sys.stdin.readlines()]
test_cases = int(lines[0])
i = 1

def min_rolls(ladders, snakes):
	board = {i: [i + n for n in range(1, 7) if i + n < 101] for i in range(1, 101)}
	weights = {}
	for (l_start, l_end) in ladders:
		board[l_start] = [l_end]
		weights[l_start, l_end] = 0
	for (s_start, s_end) in snakes:
		board[s_start] = [s_end]
		weights[s_start, s_end] = 0
	dist = djikstra(board, weights, 1)
	result = dist[100]
	return result if result != float('inf') else -1

def djikstra(graph, weights, source):
	dist = {}
	unvisited = set()
	for v in graph.keys():
		unvisited.add(v)
		if v == source:
			dist[v] = 0
		else:
			dist[v] = float('inf')
	while len(unvisited) > 0:
		closest = min(unvisited, key=lambda x: dist[x])
		unvisited.remove(closest)
		for neighbor in graph[closest]:
			path = dist[closest] + weights.get((closest, neighbor), 1)
			if path < dist[neighbor]:
				dist[neighbor] = path
	return dist
for _ in range(0, test_cases):
	n = int(lines[i])
	i += 1
	end_ladder = i + n
	ladders = [[int(l) for l in j.split()] for j in lines[i:end_ladder]]
	i = end_ladder
	m = int(lines[i])
	i += 1
	snakes = [[int(l) for l in j.split()] for j in lines[i:i + m]]
	i += m
	print(min_rolls(ladders, snakes))


def BuildGraph(L, S):
	G = [[100000 for j in range(101)] for i in range(101)]
	LS = {}
	for l in L:
		LS[l[0]] = l[1]
	for s in S:
		LS[s[0]] = s[1]
	for i in range(1, 101):
		for d in range(1, 7):
			if i + d <= 100:
				if i + d in LS:
					G[i][LS[i + d]] = 1
				else:
					G[i][i + d] = 1
	return G

def ComputeMinPath(L, S):
	G = BuildGraph(L, S)
	D = [[100000 for j in range(101)] for i in range(101)]
	for i in range(1, 101):
		D[i][i] = 0
	for i in range(1, 101):
		for j in range(1, 101):
			D[i][j] = G[i][j]
	for k in range(1, 101):
		for i in range(1, 101):
			for j in range(1, 101):
				if D[i][j] > D[i][k] + D[k][j]:
					D[i][j] = D[i][k] + D[k][j]
	if D[1][100] < 100000:
		return D[1][100]
	return -1

def main():
	T = int(input())
	for t in range(T):
		N = int(input())
		L = []
		for n in range(N):
			(start, end) = input().split()
			(start, end) = (int(start), int(end))
			L.append(list([start, end]))
		M = int(input())
		S = []
		for m in range(M):
			(start, end) = input().split()
			(start, end) = (int(start), int(end))
			S.append(list([start, end]))
		print(ComputeMinPath(L, S))
main()


for _ in range(int(input().strip())):
	move = [i for i in range(100)]
	for _ in range(int(input().strip())):
		ph = [int(i) for i in input().strip().split(' ')]
		move[ph[0] - 1] = ph[1] - 1
	for _ in range(int(input().strip())):
		ph = [int(i) for i in input().strip().split(' ')]
		move[ph[0] - 1] = ph[1] - 1
	notvis = [0] + [1] * 99
	points = [[0, 1]]
	i = 0
	trigger = 1
	while trigger:
		if len(points) == i:
			print(-1)
			break
		point = points[i]
		for j in range(1, 7):
			if move[point[0] + j] == 99:
				trigger = 0
				print(point[1])
				break
			mov = move[point[0] + j]
			if notvis[mov]:
				points.append([mov, point[1] + 1])
				notvis[mov] = 0
		i += 1


from collections import deque
from math import ceil

def leastMoves(board):
	visited = [False for i in range(107)]
	visited[1] = True
	q = deque()
	q.append((1, 0))
	while q:
		(v, d) = q.popleft()
		for i in range(1, 7):
			if not visited[v + i]:
				q.append((board[v + i], d + 1))
				if board[v + i] == 100:
					return d + 1
				visited[v + i] = True
	return -1
for _ in range(int(input())):
	board = [i for i in range(107)]
	N = int(input())
	for n in range(N):
		(a, b) = map(int, input().split())
		board[a] = b
	M = int(input())
	for m in range(M):
		(a, b) = map(int, input().split())
		board[a] = b
	ans = leastMoves(board)
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	L = [tuple((int(s) - 1 for s in input().split())) for _ in range(N)]
	M = int(input())
	S = [tuple((int(s) - 1 for s in input().split())) for _ in range(M)]
	F = list(range(100))
	D = list(range(100))
	for x in range(100):
		F[x] = x
		D[x] = -1
	for t in L + S:
		F[t[0]] = t[1]
	q = [(0, -1)]
	while len(q) > 0:
		(e, *q) = q
		f = e[0]
		d = e[1] + 1
		if D[f] == -1 or D[f] > d:
			D[f] = d
			for c in range(1, 7):
				if f + c < 100:
					q.append((F[f + c], d))
	print(D[-1])


def update_ranks(ranks, snakesladders):
	nextrank = []
	for space in ranks[-1]:
		for roll in range(1, 7):
			if space + roll <= 100:
				nextrank.append(space + roll)
	uniques = set(nextrank)
	for (start, end) in snakesladders:
		if start in uniques:
			uniques.remove(start)
			uniques.add(end)
	for rank in ranks:
		uniques = uniques - rank
	ranks.append(uniques)
	return ranks

def parse_snakes_ladders():
	nsnakes = int(input())
	snakesladders = []
	for _ in range(nsnakes):
		snake = input().split(' ')
		snakesladders.append((int(snake[0]), int(snake[1])))
	nladders = int(input())
	for _ in range(nladders):
		ladder = input().split(' ')
		snakesladders.append((int(ladder[0]), int(ladder[1])))
	return snakesladders
T = int(input())
for testcase in range(T):
	retval = -1
	snakesladders = parse_snakes_ladders()
	ranks = [set([1])]
	while len(ranks[-1]) > 0:
		ranks = update_ranks(ranks, snakesladders)
		if 100 in ranks[-1]:
			retval = len(ranks) - 1
	print(retval)


__author__ = 'peng'
import queue
ladders = []
snakes = []
game_map = {}
ladders_dic = {}
snakes_dic = {}
pred = [None] * 100

def build_graph():
	game_map[1] = 0
	for i in range(2, 101):
		game_map[i] = 100
	for l in ladders:
		ladders_dic[l[0]] = l[1]
	for s in snakes:
		snakes_dic[s[0]] = s[1]

def build_graph_bak():
	game_map[1] = 0
	for l in ladders:
		game_map[l[0]] = 100
		game_map[l[1]] = 100
	for s in snakes:
		game_map[s[0]] = 100
		game_map[s[1]] = 100

def get_weight(v, w):
	if v in ladders_dic and w == ladders_dic.get(v):
		return 0
	elif v in snakes_dic and w == snakes_dic.get(v):
		return 0
	else:
		return 1

def moved_once(current_v, next_v, pq):
	new_dist = game_map[current_v] + get_weight(current_v, next_v)
	if new_dist < game_map[next_v]:
		pred[next_v - 1] = current_v
		game_map[next_v] = new_dist
		for ent in pq.queue:
			if ent[1] == next_v:
				ent[0] = new_dist

def my_dijkstra():
	pq = queue.PriorityQueue()
	pq.put_nowait([0, 1])
	for v in range(2, 101):
		pq.put_nowait([100, v])
	while not pq.empty():
		updatePriorityQueue(pq)
		current_v = pq.get_nowait()[1]
		if current_v in ladders_dic:
			next_v = ladders_dic[current_v]
			moved_once(current_v, next_v, pq)
		elif current_v in snakes_dic:
			next_v = snakes_dic[current_v]
			moved_once(current_v, next_v, pq)
		else:
			for next_v in [x for x in range(current_v + 1, current_v + 7) if x < 101]:
				moved_once(current_v, next_v, pq)

def updatePriorityQueue(pq):
	pq.put(pq.get())

def inilize():
	ladders.clear()
	snakes.clear()
	game_map.clear()
	ladders_dic.clear()
	snakes_dic.clear()
	pred = [None] * 100

def debug_path():
	curr_v = 100
	pre_v = pred[curr_v - 1]
	while pre_v != None:
		print('back track from {} to {}'.format(curr_v, pre_v))
		curr_v = pre_v
		pre_v = pred[curr_v - 1]
t = int(input())
for i in range(t):
	inilize()
	n = int(input())
	for j in range(n):
		(ls, le) = input().split()
		(ls, le) = (int(ls), int(le))
		ladders.append((ls, le))
	m = int(input())
	for k in range(m):
		(sh, st) = input().split()
		(sh, st) = (int(sh), int(st))
		snakes.append((sh, st))
	build_graph()
	my_dijkstra()
	if game_map[100] < 100:
		print(game_map[100])
	else:
		print(-1)


import heapq

def dijkstra(links, start, target):
	v_prev = [None for x in range(100)]
	v_dist = [99999 for x in range(100)]
	v_dist[start] = 0
	prio_q = []
	heapq.heappush(prio_q, (0, start))
	while len(prio_q) > 0:
		(d, v) = heapq.heappop(prio_q)
		if v == target:
			return v_dist[v]
		for n in range(v + 1, min(v + 7, 100)):
			while n in links.keys():
				n = links[n]
			if v_dist[n] > v_dist[v] + 1:
				v_dist[n] = v_dist[v] + 1
				v_prev[n] = v
				heapq.heappush(prio_q, (v_dist[n], n))
	return -1

def play():
	n = int(input())
	links = {}
	for i in range(n):
		(s, e) = [int(x) for x in input().split()]
		links[s - 1] = e - 1
	m = int(input())
	for i in range(m):
		(s, e) = [int(x) for x in input().split()]
		links[s - 1] = e - 1
	print(dijkstra(links, 0, 99))
t = int(input())
for i in range(t):
	play()


class Snake:

	def __init__(self, start, end):
		self.start = start
		self.end = end

class Ladder:

	def __init__(self, start, end):
		self.start = start
		self.end = end

class GameBoard:

	def __init__(self):
		self.ladders = set()
		self.snakes = set()

def recursive_snakes(board, position, roll_count, best_roll_count, history):
	if position in history and roll_count >= history[position]:
		return (best_roll_count, history)
	elif best_roll_count != None and roll_count >= best_roll_count:
		return (best_roll_count, history)
	elif position == 100:
		history[position] = roll_count
		if best_roll_count == None or roll_count < best_roll_count:
			best_roll_count = roll_count
		return (best_roll_count, history)
	else:
		history[position] = roll_count
		for roll in range(1, 7):
			new_position = roll + position
			for ladder in board.ladders:
				if new_position == ladder.start:
					new_position = ladder.end
					break
			for snake in board.snakes:
				if new_position == snake.start:
					new_position = snake.end
					break
			if new_position > 100:
				break
			else:
				(best_roll_count, history) = recursive_snakes(board, new_position, roll_count + 1, best_roll_count, history)
		return (best_roll_count, history)
T = int(input())
for _ in range(T):
	game_board = GameBoard()
	num_ladders = int(input())
	for _ in range(num_ladders):
		(s, e) = list(map(int, input().split()))
		ladder = Ladder(s, e)
		game_board.ladders.add(ladder)
	num_snakes = int(input())
	for _ in range(num_snakes):
		(s, e) = list(map(int, input().split()))
		snake = Snake(s, e)
		game_board.snakes.add(snake)
	(best_roll_count, history) = recursive_snakes(game_board, 1, 0, None, {})
	if best_roll_count == None:
		print(-1)
	else:
		print(best_roll_count)


def loadSOrL(n, sOrL):
	for l in range(0, n):
		(start, end) = [int(i) for i in input().split(' ') if i != '']
		sOrL[start] = end
tests = int(input())
for t in range(0, tests):
	sOrL = {}
	loadSOrL(int(input()), sOrL)
	loadSOrL(int(input()), sOrL)
	state = (1, 0)
	from collections import deque
	q = deque()
	q.append(state)
	shortestPath = {}
	solFound = False
	while len(q) > 0:
		state = q.popleft()
		(currLoc, currRolls) = state
		for diceVal in range(1, 7):
			newLoc = currLoc + diceVal
			newRolls = currRolls + 1
			if newLoc in sOrL:
				newLoc = sOrL[newLoc]
			if newLoc == 100:
				print(newRolls)
				q.clear()
				solFound = True
				break
			else:
				if newLoc in shortestPath:
					if shortestPath[newLoc] >= newRolls:
						shortestPath[newLoc] = newRolls
					else:
						continue
				else:
					shortestPath[newLoc] = currRolls + 1
				newState = (newLoc, newRolls)
				q.append(newState)
	if solFound == False:
		print(-1)


from itertools import chain
from collections import defaultdict
from collections import deque
_BOARD_SIZE = 100
_MAX_DICE = 6

def _fill_board(board_size, snakes, ladders):
	board = defaultdict(set)
	for i in range(1, board_size + 1):
		for j in range(1, _MAX_DICE + 1):
			if i + j <= board_size:
				board[i].add(i + j)
	for (start, end) in snakes:
		board[start] = set((end,))
	for (start, end) in ladders:
		board[start] = set((end,))
	return board

def _get_shortest_path(board, snakes, ladders, source, destination):
	prev = [-1 for _ in range(_BOARD_SIZE + 1)]
	(seen, q) = (set(), deque())
	q.append(source)
	while q:
		curr_node = q.popleft()
		if curr_node == destination:
			break
		for node in board[curr_node]:
			if node not in seen:
				seen.add(node)
				q.append(node)
				prev[node] = curr_node
	if curr_node != destination:
		return -1
	pathlen = 0
	curr_node = destination
	snakes = {s for (s, _) in snakes}
	ladders = {s for (s, _) in ladders}
	while curr_node != 1:
		dest = prev[curr_node]
		if dest not in snakes and dest not in ladders:
			pathlen += 1
		curr_node = dest
	return pathlen

def min_throws(board_size, snakes, ladders):
	board = _fill_board(board_size, snakes, ladders)
	return _get_shortest_path(board, snakes, ladders, 1, _BOARD_SIZE)
n = int(input())
for _ in range(n):
	ladders = []
	num_ladders = int(input())
	for _ in range(num_ladders):
		(s, e) = [int(el) for el in input().split()]
		ladders.append((s, e))
	snakes = []
	num_snakes = int(input())
	for _ in range(num_snakes):
		(s, e) = [int(el) for el in input().split()]
		snakes.append((s, e))
	print(min_throws(_BOARD_SIZE, snakes, ladders))


def readInput():
	T = int(input())
	for _ in range(T):
		N = int(input())
		ladders = dict((map(int, input().split()) for _ in range(N)))
		M = int(input())
		snakes = dict((map(int, input().split()) for _ in range(M)))
		yield (snakes, ladders)

def solve(snakes, ladders):
	seen = [False for _ in range(101)]

	def go(current, new):
		if new in snakes:
			return snakes[new]
		if new in ladders:
			return ladders[new]
		if new > 100:
			return current
		return new
	toProcess = [(1, 0)]
	while toProcess:
		nextSquares = []
		for (sq, moves) in toProcess:
			if sq == 100:
				return moves
			if seen[sq]:
				continue
			nextSquares.extend(((go(sq, sq + dice), moves + 1) for dice in range(1, 7)))
			seen[sq] = True
		toProcess = nextSquares
	return -1
for (snakes, ladders) in readInput():
	print(solve(snakes, ladders))


def solve(board):
	frontier = [1]
	visited = {}
	visited[1] = 0
	goal = 100
	while frontier:
		curr = frontier.pop(0)
		for _next in board[curr]:
			if _next == goal:
				if len(board[curr]) == 1 and curr != 99:
					return visited[curr]
				else:
					return visited[curr] + 1
			if _next not in visited:
				if len(board[curr]) == 1 and curr != 99:
					visited[_next] = visited[curr]
				else:
					visited[_next] = visited[curr] + 1
				frontier.append(_next)
	return -1
numTests = int(input())
for test_i in range(numTests):
	board = {}
	numLadders = int(input())
	for ladder_i in range(numLadders):
		(a, b) = (int(_) for _ in input().split())
		board[a] = [b]
	numSnakes = int(input())
	for snake_i in range(numSnakes):
		(a, b) = (int(_) for _ in input().split())
		board[a] = [b]
	for x in range(1, 101):
		if x not in board:
			board[x] = []
			for offset in range(1, 7):
				if offset + x <= 100:
					board[x].append(offset + x)
	solution = solve(board)
	print(solution)


graphDict = {}
test = int(input())
ladDict = {}
dist = {}
prev = {}

def dijsktra():
	Q = []
	dist[1] = 0
	prev[1] = -1
	for i in range(1, 101):
		if i != 1:
			dist[i] = -1
			prev[i] = -1
		Q.append(i)
	while len(Q) > 0:
		mini = dist[Q[0]]
		u = Q[0]
		for q in Q:
			if mini > dist[q] and dist[q] != -1:
				mini = dist[q]
				u = q
		Q.remove(u)
		for v in graphDict[u]:
			alt = dist[u] + 1
			if alt < dist[v] or dist[v] == -1:
				if v not in range(u + 1, u + 7):
					dist[v] = dist[u]
				else:
					dist[v] = alt
				prev[v] = u
for i in range(0, test):
	graphDict.clear()
	ladDict.clear()
	dist.clear()
	prev.clear()
	ladders = int(input())
	for i in range(0, ladders):
		(x, y) = input().split()
		x = int(x)
		y = int(y)
		ladDict[x] = y
	snakes = int(input())
	snakeDict = {}
	for i in range(0, snakes):
		(x, y) = input().split()
		x = int(x)
		y = int(y)
		snakeDict[x] = y
	for i in range(1, 101):
		graphDict[i] = []
		if i not in ladDict.keys() and i not in snakeDict.keys():
			for j in range(i + 1, i + 7):
				if j <= 100:
					graphDict[i].append(j)
		else:
			if i in ladDict.keys():
				graphDict[i] = [ladDict[i]] + graphDict[i]
			if i in snakeDict.keys():
				graphDict[i] = [snakeDict[i]] + graphDict[i]
	dijsktra()
	print(dist[100])


from collections import deque
MAX = 100

class Field:

	def __init__(self):
		self.snakes = {}
		self.ladders = {}
		for d in [self.ladders, self.snakes]:
			for _ in range(int(input())):
				(start, end) = [int(s) for s in input().split()]
				d[start] = end

	def neighbors(self, element):
		for n in range(element + 1, min(MAX + 1, element + 7)):
			if n in self.snakes:
				yield self.snakes[n]
			elif n in self.ladders:
				yield self.ladders[n]
			else:
				yield n

	def shortest(self):
		visited = (MAX + 1) * [False]
		fifo = deque([(1, 0)])
		visited[1] = True
		while fifo:
			(el, steps) = fifo.popleft()
			for n in self.neighbors(el):
				if n == MAX:
					return steps + 1
				if not visited[n]:
					fifo.append((n, steps + 1))
					visited[n] = True
		return -1
for _ in range(int(input())):
	print(Field().shortest())


import sys, logging, heapq
from collections import defaultdict
LOGLEVEL = logging.WARN
(START_V, END_V) = (1, 100)
(MIN_JUMP, MAX_JUMP) = (1, 6)
EMPTY_TUPLE = tuple()
(LADDERS, SNAKES) = (1, 2)

def read_edges(stream, kind, prev_edge_list):
	assert kind in (LADDERS, SNAKES)
	read = lambda : stream.readline().strip()
	prev_starts = set((e[0] for e in prev_edge_list))
	seen = set()
	n = int(read())
	assert 1 <= n and n <= 15
	for _ in range(n):
		(v, w) = (int(x) for x in read().split())
		assert v != w
		assert not v in seen
		seen.add(v)
		if kind == LADDERS:
			assert START_V < v and v < w and (w <= END_V)
		else:
			assert START_V <= w and w < v and (v < END_V)
		assert not w in prev_starts
		yield (v, w)

class Graph(object):

	def __init__(self, stream=sys.stdin):
		ladders = read_edges(stream, LADDERS, EMPTY_TUPLE)
		snakes = read_edges(stream, SNAKES, ladders)
		self.ladders = dict(ladders)
		self.snakes = dict(snakes)

	def adj(self, v):
		assert START_V <= v and v <= END_V
		w = self.ladders.get(v, None) or self.snakes.get(v, None)
		if w:
			yield (w, 0)
		else:
			for w in range(v + MIN_JUMP, min(v + MAX_JUMP + 1, END_V + 1)):
				yield (w, 1)

	def __str__(self):
		lines = []
		for v in range(START_V, END_V + 1):
			adj = list(self.adj(v))
			lines.append('%s: %s' % (v, adj))
		return '\n'.join(lines)

def parse_graphs(stream=sys.stdin):
	t = int(stream.readline().strip())
	assert 1 <= t and t <= 10
	for _ in range(t):
		yield Graph(stream)

def shortest_path(g, source=START_V, target=END_V):
	(q, seen) = ([(0, source, [])], set())
	while q:
		(cost, v, path) = heapq.heappop(q)
		if not v in seen:
			seen.add(v)
			path = path + [v]
			if v == target:
				return (cost, path)
			for (w, w_cost) in g.adj(v):
				heapq.heappush(q, (cost + w_cost, w, path))
	return (-1, [])

def main():
	logging.basicConfig(level=LOGLEVEL, format='%(message)s')
	for (i, g) in enumerate(parse_graphs()):
		logging.debug('graph #%d:\n%s', i, g)
		(cost, path) = shortest_path(g)
		logging.debug('=> %r rolls via %r', cost, path)
		print(cost)
main()


def bfs():
	visited = {}
	for i in range(1, 107):
		visited[i] = 0
	ans = -1
	q = []
	q.insert(0, [1, 0])
	while q:
		u = q.pop()
		if visited[u[0]] == 0:
			visited[u[0]] = 1
			if u[0] == 100:
				ans = u[1]
				break
			for i in d[u[0]]:
				if visited[i] == 0:
					if check[u[0]] == [0, 0]:
						q.insert(0, [i, u[1] + 1])
					else:
						q.insert(0, [i, u[1]])
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	l = []
	check = {}
	for j in range(1, 107):
		check[j] = [0, 0]
	for j in range(n):
		l.append([int(k) for k in input().split()])
		check[l[-1][0]] = [1, l[-1][1]]
	m = int(input())
	s = []
	for j in range(m):
		s.append([int(k) for k in input().split()])
		check[s[-1][0]] = [2, s[-1][1]]
	d = {}
	for j in range(1, 101):
		if check[j][0] == 0:
			d[j] = [j + 1, j + 2, j + 3, j + 4, j + 5, j + 6]
		else:
			d[j] = [check[j][1]]
	print(bfs())


n = input()
for _ in range(int(n)):
	x = input()
	ladder = {}
	for _ in range(int(x)):
		(start, end) = input().split()
		ladder[int(start)] = int(end)
	y = input()
	snake = {}
	for _ in range(int(y)):
		(start, end) = input().split()
		snake[int(start)] = int(end)
	current = 0
	best = [0] * 101
	possible = True
	i = 1
	while i < 100 and possible:
		snakecount = 0
		current = best[i]
		if current != 'snake':
			cont = True
			for roll in range(1, 7):
				if cont:
					to_check = i + roll
					if to_check < 101 and to_check not in snake:
						if best[to_check] == 0:
							best[to_check] = 1 + current
						else:
							best[to_check] = min(best[to_check], 1 + current)
							if to_check in ladder:
								best[ladder[to_check]] = best[to_check]
					elif to_check in snake:
						best[to_check] = 'snake'
						snakecount += 1
						if 1 + current < best[snake[to_check]]:
							best[snake[to_check]] = 1 + current
							i = snake[to_check] - 1
							cont = False
						if snakecount == 6:
							possible = False
							print(-1)
		i += 1
	if possible:
		print(best[100])


def snakesandladders(top, jump):
	start = {1}
	path = {1: ()}
	while len(start) > 0:
		i = start.pop()
		p = path[i] + (i,)
		for j in range(i + 1, i + 7):
			if j > top:
				return len(path[top])
			if j in jump:
				j = jump[j]
			if j not in path or len(path[j]) > len(p):
				start.add(j)
				path[j] = p
	return -1
T = int(input())
for index in range(0, T):
	l = int(input())
	jumps = {}
	for index2 in range(0, l):
		arin = input().split(' ')
		jumps[int(arin[0])] = int(arin[1])
	s = int(input())
	for index2 in range(0, s):
		arin = input().split(' ')
		jumps[int(arin[0])] = int(arin[1])
	print(snakesandladders(100, jumps))


def snakesandladders(top, jump):
	start = {1}
	path = {1: ()}
	while len(start) > 0:
		i = start.pop()
		p = path[i] + (i,)
		for j in range(i + 1, i + 7):
			if j > top:
				return len(path[top])
			if j in jump:
				j = jump[j]
			if j not in path or len(path[j]) > len(p):
				start.add(j)
				path[j] = p
	return -1
T = int(input())
for index in range(0, T):
	l = int(input())
	jumps = {}
	for index2 in range(0, l):
		arin = input().split(' ')
		jumps[int(arin[0])] = int(arin[1])
	s = int(input())
	for index2 in range(0, s):
		arin = input().split(' ')
		jumps[int(arin[0])] = int(arin[1])
	print(snakesandladders(100, jumps))


T = int(input())
for t in range(T):
	ladder_snake = [0 for i in range(101)]
	N = int(input())
	for n in range(N):
		(start, end) = map(int, input().split())
		ladder_snake[start] = end
	M = int(input())
	for m in range(M):
		(start, end) = map(int, input().split())
		ladder_snake[start] = end
	visited = [False for i in range(101)]
	step = [0 for i in range(101)]
	Q = [1]
	answer = -1
	while Q:
		cur = Q.pop(0)
		visited[cur] = True
		if cur == 100:
			answer = step[cur]
			break
		for i in range(1, 7):
			nex = cur + i
			if nex > 100:
				continue
			if ladder_snake[nex]:
				nex = ladder_snake[nex]
			if visited[nex]:
				continue
			visited[nex] = True
			step[nex] = step[cur] + 1
			Q += [nex]
	print(answer)


from collections import defaultdict
import heapq

def dijkstra(S, N, G):
	D = {}
	H = [(0, S)]
	for n in range(1, N + 1):
		D[n] = 999999
	D[S] = 0
	while H:
		t = heapq.heappop(H)
		for h in G[t[1]]:
			if D[h[1]] > D[t[1]] + h[0]:
				D[h[1]] = D[t[1]] + h[0]
				if h in H:
					H.remove(h)
					heapq.heapify(H)
				heapq.heappush(H, (D[h[1]], h[1]))
	return D[100]

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		S = {}
		for _ in range(N):
			e = [int(i) for i in input().split()]
			S[e[0]] = e[1]
		M = int(input())
		L = {}
		for _ in range(M):
			e = [int(i) for i in input().split()]
			L[e[0]] = e[1]
		G = defaultdict(set)
		for i in range(1, 101):
			for j in range(i + 1, i + 7):
				if j <= 100:
					if j in S:
						G[i].add((1, S[j]))
					elif j in L:
						G[i].add((1, L[j]))
					else:
						G[i].add((1, j))
		D = dijkstra(1, 100, G)
		print(D if D != 999999 else '-1')
main()


num_tc = int(input())
for i in range(num_tc):
	short_cuts = {}
	num_ladders = int(input())
	for i in range(num_ladders):
		(src, dest) = (int(x) for x in input().split())
		short_cuts[src] = dest
	num_snakes = int(input())
	for i in range(num_snakes):
		(src, dest) = (int(x) for x in input().split())
		short_cuts[src] = dest
	distance = {1: 0}
	fringe = [1]
	while len(fringe) > 0:
		curr_idx = fringe.pop(0)
		curr_dist = distance[curr_idx]
		if curr_idx == 100:
			print(curr_dist)
			break
		elif curr_idx > 100:
			continue
		else:
			for i in range(curr_idx + 1, curr_idx + 7):
				if i in short_cuts:
					if short_cuts[i] not in distance:
						fringe.append(short_cuts[i])
						distance[short_cuts[i]] = curr_dist + 1
				elif i not in distance:
					fringe.append(i)
					distance[i] = curr_dist + 1
	if len(fringe) == 0:
		print(-1)


NUM_CELLS = 100
for testcase in range(int(input())):
	dest = [i for i in range(NUM_CELLS + 1)]
	min_moves = [1 << 32] * (NUM_CELLS + 1)
	min_moves[1] = 0
	N = int(input())
	for _ in range(N):
		(f, to) = [int(x) for x in input().split()]
		dest[f] = to
	M = int(input())
	for _ in range(M):
		(f, to) = [int(x) for x in input().split()]
		dest[f] = to
	changed = True
	while changed:
		changed = False
		for i in range(1, NUM_CELLS + 1):
			for diceroll in range(i + 1, min(NUM_CELLS + 1, i + 7)):
				if dest[i] == i and min_moves[i] + 1 < min_moves[diceroll]:
					changed = True
					min_moves[diceroll] = min_moves[i] + 1
				if dest[diceroll] != diceroll and min_moves[diceroll] < min_moves[dest[diceroll]]:
					changed = True
					min_moves[dest[diceroll]] = min_moves[diceroll]
	if min_moves[NUM_CELLS] == 1 << 32:
		print(-1)
	else:
		print(min_moves[NUM_CELLS])


class vertex:

	def __init__(self):
		self.adj = []
		self.level = -1
T = int(input())
for i in range(0, T):
	ladders_and_snakes = {}
	num_ladders = int(input())
	for i in range(0, num_ladders):
		var = input().split()
		(u, v) = (int(var[0]), int(var[1]))
		ladders_and_snakes[u] = v
	num_snakes = int(input())
	for i in range(0, num_snakes):
		var = input().split()
		(u, v) = (int(var[0]), int(var[1]))
		ladders_and_snakes[u] = v
	V = []
	for i in range(0, 101):
		V.append(vertex())
	for i in range(1, 101):
		for dice in range(1, 7):
			if i + dice > 100:
				break
			else:
				target = i + dice
				if target in ladders_and_snakes:
					target = ladders_and_snakes[i + dice]
				V[i].adj.append(V[target])
	visit = [V[1]]
	current_level = 0
	while len(visit) != 0:
		next = []
		for u in visit:
			if u.level == -1:
				u.level = current_level
				for v in u.adj:
					next.append(v)
		current_level += 1
		visit = next
	print(V[100].level)


test_cases = int(input().strip())
for test_case in range(test_cases):
	snake_count = int(input().strip())
	shortcuts = {}
	for snake in range(snake_count):
		(src, dst) = [int(item) - 1 for item in input().strip().split()]
		shortcuts[src] = dst
	ladder_count = int(input().strip())
	for ladder in range(ladder_count):
		(src, dst) = [int(item) - 1 for item in input().strip().split()]
		shortcuts[src] = dst
	board = [0] + [None] * 99
	dst = 0
	while dst < 99:
		dst += 1
		moves = board[dst]
		sources = [cell for cell in board[max(dst - 6, 0):dst] if cell is not None]
		if not sources:
			continue
		moves = min(sources) + 1
		new_dst = shortcuts.get(dst, dst)
		if board[new_dst] is None or moves < board[new_dst]:
			board[new_dst] = moves
			dst = min(dst, new_dst)
	print(board[-1] if board[-1] is not None else '-1')


def infmin(iterable):
	r = None
	for x in iterable:
		if r is None:
			r = x
		elif x is not None:
			r = min(x, r)
	return r

def buildGraph(l):
	return [[(l[i], 0)] if i in l else [(j + i, 1) for j in range(1, 7) if i + j < 100] for i in range(100)]

class PriorityQueue:

	def __init__(self, capacity, comparator):
		self.__q = [None] * capacity
		self.__cmp = comparator
		self.__cnt = 0

	def put(self, item):
		self.__q[self.__cnt] = item
		self.__cnt += 1
		self.__heapify(self.__cnt - 1)

	def take(self):
		r = self.__q[0]
		self.__cnt -= 1
		self.__q[0] = self.__q[self.__cnt]
		self.__siftDown(0)
		return r

	def modify(self, selector, new):
		for i in range(self.__cnt):
			if selector(self.__q[i]):
				self.__q[i] = new
				self.__siftDown(i)
				self.__heapify(i)
				return
		self.put(new)

	def isEmpty(self):
		return self.__cnt == 0

	def __parent(self, i):
		return (i - 1) // 2

	def __left(self, i):
		c = i * 2 + 1
		if c < self.__cnt:
			return c
		else:
			return None

	def __right(self, i):
		c = i * 2 + 2
		if c < self.__cnt:
			return c
		else:
			return None

	def __inOrder(self, parent, child):
		return self.__cmp(self.__q[parent], self.__q[child])

	def __sort2(self, a, b):
		if self.__cmp(self.__q[a], self.__q[b]):
			return (a, b)
		else:
			return (b, a)

	def __heapify(self, i):
		while i > 0:
			p = self.__parent(i)
			if not self.__inOrder(p, i):
				(self.__q[p], self.__q[i]) = (self.__q[i], self.__q[p])
				i = p
			else:
				return

	def __siftDown(self, i):
		while i is not None:
			l = self.__left(i)
			r = self.__right(i)
			if l is None and r is None:
				return
			p = l
			if r is not None:
				(l, r) = self.__sort2(l, r)
				orders = [self.__inOrder(i, l), self.__inOrder(i, r)]
				if all(orders):
					return
				elif orders[0] == False:
					p = l
				else:
					p = r
			if self.__inOrder(i, p):
				return
			(self.__q[p], self.__q[i]) = (self.__q[i], self.__q[p])
			i = p

def lessinf(a, b):
	return a is not None and (b is None or a < b)

def dijkstra(g, s, dst):
	visited = [False] * len(g)
	visited[s] = True
	dist = [None] * len(g)
	dist[0] = 0
	q = PriorityQueue(len(g), lambda a, b: lessinf(a[0], b[0]))
	for i in range(len(g)):
		q.put((dist[i], i))
	while not q.isEmpty():
		(d, current) = q.take()
		for (v, w) in g[current]:
			a = d + w
			if not visited[v] and lessinf(a, dist[v]):
				dist[v] = a
				q.modify(lambda x: x[1] == v, (a, v))
		visited[current] = True
		if current == dst:
			return dist
	return dist
t = int(input())
for _ in range(t):
	n = int(input())
	l = dict()
	for __ in range(n):
		(f, t) = [int(x) - 1 for x in input().split()]
		l[f] = t
	m = int(input())
	for __ in range(m):
		(f, t) = [int(x) - 1 for x in input().split()]
		l[f] = t
	g = buildGraph(l)
	d = dijkstra(g, 0, 99)
	print(d[99] if d[99] is not None else -1)