Given a 5x6 snakes and ladders board, find the minimum number of dice throws required to reach the destination or last cell (30^{th} cell) from the source (1st cell). 
You are given an integer N denoting the total number of snakes and ladders and an array arr[] of 2*N size where 2*i and (2*i + 1)^{th} values denote the starting and ending point respectively of i^{th }snake or ladder. The board looks like the following.
Note: Assume that you have complete control over the 6 sided dice. No ladder starts from 1st cell.
                                   
Example 1:
Input:
N = 8
arr[] = {3, 22, 5, 8, 11, 26, 20, 29, 
       17, 4, 19, 7, 27, 1, 21, 9}
Output: 3
Explanation:
The given board is the board shown
in the figure. For the above board 
output will be 3. 
a) For 1st throw get a 2. 
b) For 2nd throw get a 6.
c) For 3rd throw get a 2.
Your Task:
You do not need to read input or print anything. Your task is to complete the function minThrow() which takes N and arr as input parameters and returns the minimum number of throws required to reach the end of the game.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10
1 ≤ arr[i] ≤ 30

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Graph algorithms

Data structures

Graph traversal

Starter code: # User function Template for Python3



class Solution:

    def minThrow(self, N, arr):

        # code here

Solutions:
from collections import deque

class Solution:

	def minThrow(self, N, arr):
		snakes_ladders = {}
		for i in range(0, 2 * N, 2):
			snakes_ladders[arr[i]] = arr[i + 1]
		q = deque([(1, 0)])
		visited = set([1])
		while q:
			(curr_pos, num_throws) = q.popleft()
			if curr_pos == 30:
				return num_throws
			for i in range(1, 7):
				next_pos = curr_pos + i
				if next_pos > 30:
					continue
				if next_pos in snakes_ladders:
					next_pos = snakes_ladders[next_pos]
				if next_pos not in visited:
					visited.add(next_pos)
					q.append((next_pos, num_throws + 1))
		return -1


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		d = {}
		i = 0
		while i < len(arr) - 1:
			d[arr[i]] = arr[i + 1]
			i += 2
		vis = [False] * 31
		q = deque()
		q.append([1, 0])
		vis[1] = True
		while q:
			(node, step) = q.popleft()
			if node == 30:
				return step
			for i in range(1, 7):
				newnode = node + i
				if newnode <= 30 and vis[newnode] == False:
					if newnode in d:
						q.append([d[newnode], step + 1])
					else:
						q.append([newnode, step + 1])
					vis[newnode] = True
		return -1


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		dct = {}
		for i in range(0, 2 * N, 2):
			dct[arr[i]] = arr[i + 1]
		q = deque()
		q.append((1, 0))
		while q:
			pos = q.popleft()
			if pos[0] >= 30:
				return pos[1]
			for i in range(1, 7):
				k = i + pos[0]
				if k in dct:
					k = dct[k]
				q.append((k, 1 + pos[1]))
		return -1


from queue import Queue

class Solution:

	def minThrow(self, N, arr):
		self.mapper = {}
		self.visited = [False] * 31
		for i in range(0, 2 * N, 2):
			self.mapper.update({arr[i]: arr[i + 1]})
		self.q = Queue()
		self.q.put(1)
		self.q.put(-1)
		return self.findMin()

	def findMin(self):
		throw = 1
		while not self.q.empty():
			ele = self.q.get()
			self.visited[ele] = True
			if ele == -1:
				throw = throw + 1
				self.q.put(-1)
				continue
			for i in range(1, 7):
				final_step = self.move(ele, i)
				if final_step == 30:
					return throw

	def move(self, ele, step):
		final_step = ele + step
		if final_step > 30:
			return None
		final_step = self.mapper.get(final_step, final_step)
		if not self.visited[final_step]:
			self.q.put(final_step)
		return final_step


from collections import defaultdict, deque

class Solution:

	def minThrow(self, N, arr):
		board = [0] * 31
		for i in range(0, 2 * N, 2):
			board[arr[i]] = arr[i + 1] - arr[i]
		visited = [False] * 31
		queue = deque([(1, 0)])
		while queue:
			(curr_cell, throws) = queue.popleft()
			if curr_cell == 30:
				return throws
			visited[curr_cell] = True
			for i in range(1, 7):
				next_cell = curr_cell + i
				if next_cell <= 30:
					next_cell += board[next_cell]
					if not visited[next_cell]:
						visited[next_cell] = True
						queue.append((next_cell, throws + 1))


from collections import deque

class Solution:

	def adj(self, data, dist, start, dest, ld, sn):
		q = deque([start])
		visited = set()
		while len(q) != 0:
			node = q.popleft()
			visited.add(node)
			(prev, prev_dist) = (node, dist[node][0])
			for each in data[node]:
				if each not in visited:
					if prev in ld and each == ld[prev]:
						dist[each][0] = prev_dist
						q.append(each)
					elif each in sn:
						dist[each][0] = float('inf')
					elif dist[each][0] > prev_dist + 1:
						dist[each][0] = prev_dist + 1
						q.append(each)
				elif prev_dist + 1 < dist[each][0] and each not in sn:
					dist[each][0] = prev_dist + 1
					q.append(each)
		return 0

	def minThrow(self, N, arr):
		(ld, sn) = ({}, {})
		n = len(arr)
		for i in range(0, len(arr) - 1, 2):
			if arr[i] > arr[i + 1]:
				sn[arr[i]] = arr[i + 1]
			elif arr[i] < arr[i + 1]:
				ld[arr[i]] = arr[i + 1]
		data = {}
		data[30] = [None]
		for i in range(24):
			data[i + 1] = [i + 2, i + 3, i + 4, i + 5, i + 6, i + 7]
		data[25] = [26, 27, 28, 29, 30]
		data[26] = [27, 28, 29, 30]
		data[27] = [28, 29, 30]
		data[28] = [29, 30]
		data[29] = [30]
		data[30] = []
		for (a, b) in ld.items():
			data[a].append(b)
		for (a, b) in sn.items():
			data[a].append(b)
		dist = [[float('inf'), i] for i in range(31)]
		dist[1] = [0, 1]
		self.adj(data, dist, 1, 30, ld, sn)
		return dist[-1][0]


import collections

class Solution:

	def minThrow(self, N, arr):

		def build_board(N, arr):
			board = [i for i in range(31)]
			for i in range(0, 2 * N, 2):
				board[arr[i]] = arr[i + 1]
			return board

		def bfs(board):
			visited = [False] * 31
			queue = collections.deque([(1, 0)])
			visited[1] = True
			while queue:
				(cell, throws) = queue.popleft()
				if cell == 30:
					return throws
				for i in range(1, 7):
					next_cell = cell + i
					if next_cell <= 30:
						next_cell = board[next_cell]
						if not visited[next_cell]:
							visited[next_cell] = True
							queue.append((next_cell, throws + 1))
			return -1
		board = build_board(N, arr)
		return bfs(board)


class Solution:

	def minThrow(self, N, arr):
		mpl = [0 for i in range(31)]
		for i in range(0, 2 * N, 2):
			mpl[arr[i]] = arr[i + 1]
		ans = c = 0
		flag = 0
		q = []
		q.append(1)
		vis = [0 for j in range(31)]
		vis[1] = 1
		while c < 10:
			t = []
			for i in range(len(q)):
				x = q[i]
				for j in range(1, 7):
					if vis[30] == 1:
						return ans + 1
					if x + j < 30 and mpl[x + j] != 0 and (vis[mpl[x + j]] == 0):
						t.append(mpl[x + j])
						vis[mpl[x + j]] = 1
					elif mpl[x + j] == 0 and vis[x + j] == 0:
						t.append(x + j)
						vis[x + j] = 1
					if vis[30] == 1:
						return ans + 1
			q = t
			ans += 1
			c += 1


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		moves = [-1 for i in range(35)]
		vis = [False for i in range(35)]
		i = 0
		while i < 2 * N:
			moves[arr[i]] = arr[i + 1]
			i += 2
		q = deque()
		q.append([1, 0])
		vis[1] = True
		while len(q):
			p = q.popleft()
			ii = p[0]
			ss = p[1]
			if ii == 30:
				break
			for i in range(ii + 1, ii + 7):
				if i > 30:
					break
				pp = [0] * 2
				if vis[i] == False:
					vis[i] = True
					pp[1] = ss + 1
					if moves[i] != -1:
						pp[0] = moves[i]
					else:
						pp[0] = i
					q.append(pp)
		return p[1]


class Solution:

	def minThrow(self, N, arr):
		dic = {}
		for i in range(0, 2 * N, 2):
			dic[arr[i]] = arr[i + 1]
		queue = []
		queue.append((1, 0))
		while queue:
			peek = queue.pop(0)
			if peek[0] >= 30:
				return peek[1]
			for i in range(1, 7):
				val = i + peek[0]
				if val in dic:
					val = dic[val]
				queue.append((val, 1 + peek[1]))
		return -1


class Solution:

	def minThrow(self, N, arr):
		edges = dict()
		i = 0
		while i < len(arr):
			if arr[i] in edges:
				ar = edges[arr[i]]
				ar.append(arr[i + 1])
			else:
				edges[arr[i]] = [arr[i + 1]]
			i += 2
		distance = [float('+inf')] * 30
		distance[0] = 0
		q = [1]
		visited = dict()
		while q:
			ver = q.pop(0)
			visited[ver] = True
			i = ver + 1
			while i < ver + 6 + 1 and i < 31:
				if i not in visited:
					q.append(i)
					visited[i] = True
					distance[i - 1] = distance[ver - 1] + 1
					if i in edges:
						for edge in edges[i]:
							if edge not in visited:
								q.append(edge)
								visited[edge] = True
								distance[edge - 1] = distance[i - 1]
				i += 1
		return distance[29]


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		c = {}
		self.mini = 9999999999
		for i in range(N):
			start = arr[2 * i]
			end = arr[2 * i + 1]
			c[start] = end
		q = deque()
		q.appendleft((1, 0))
		while q:
			(curr, moves) = q.pop()
			for k in range(1, 7):
				new = curr + k
				if new >= 30:
					return moves + 1
				if new in c:
					q.appendleft((c[new], moves + 1))
				else:
					q.appendleft((new, moves + 1))


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		target = 30
		graph = {}
		for i in range(N):
			graph[arr[2 * i]] = arr[2 * i + 1]
		visit = {u: False for u in range(1, target + 1)}
		Q = deque([[1, 0]])
		while Q:
			(pos, move) = Q.popleft()
			if pos == target:
				return move
			if visit[pos]:
				continue
			visit[pos] = True
			for m in range(1, 7):
				newPos = pos + m
				if newPos > target:
					break
				if newPos in graph:
					newPos = graph[newPos]
				Q.append([newPos, move + 1])
		return -1


class Solution:

	def minThrow(self, N, arr):
		from collections import deque
		d = {}
		for i in range(0, 2 * N, 2):
			d[arr[i]] = arr[i + 1]
		q = deque([[1, 0]])
		v = set()
		while q:
			(x, ans) = q.popleft()
			if x >= 30:
				return ans
			for i in range(1, 7):
				if x + i not in v:
					if x + i in d:
						q.append([d[x + i], ans + 1])
					else:
						q.append([x + i, ans + 1])
					v.add(x + i)
		return -1


class Solution:

	def minThrow(self, N, arr):
		d_up = {}
		d_down = {}
		for i in range(0, len(arr), 2):
			if arr[i] < arr[i + 1]:
				d_up[arr[i]] = arr[i + 1]
			else:
				d_down[arr[i]] = arr[i + 1]
		count = self.shortestsum(d_up, d_down, arr, 1, 30)
		start = -1
		end = -1
		ma = 0
		temp_count = 0
		for i in d_up:
			if d_up[i] - i > ma:
				start = i
				end = d_up[i]
				ma = d_up[i] - i
		temp_count += self.shortestsum(d_up, d_down, arr, 1, start)
		temp_count += 1
		temp_count += self.shortestsum(d_up, d_down, arr, end, 30)
		if temp_count < count:
			return temp_count
		return count

	def shortestsum(self, d_up, d_down, arr, current, end):
		count = 0
		while current < end:
			ma = current
			for i in range(0, 6 + 1):
				temp = current + i
				if temp in d_up:
					if d_up[temp] > ma:
						ma = d_up[temp]
				elif temp not in d_down:
					if temp > ma:
						ma = temp
			current = ma
			count += 1
		return count


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		q = deque()
		vis = set()
		d = {}
		for i in range(0, len(arr), 2):
			key = arr[i]
			value = arr[i + 1]
			d[key] = value
		q.appendleft(1)
		q.appendleft(None)
		level = 0
		while q:
			curr = q.pop()
			if curr:
				if curr in vis:
					continue
				vis.add(curr)
				if curr == 30:
					return level
				for i in range(1, 7):
					child = curr + i
					if child in d:
						child = d[child]
					if child not in vis:
						q.appendleft(child)
			else:
				if not q:
					return -1
				level += 1
				q.appendleft(None)


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		e = [[] for i in range(31)]
		d = {}
		for k in range(N):
			i = 2 * k
			j = i + 1
			i = arr[i]
			j = arr[j]
			d[i] = j
		for i in range(1, 30):
			for j in range(i + 1, i + 7):
				if j <= 30:
					if j in d:
						j = d[j]
					e[i].append(j)
		c = ['w' for i in range(31)]
		d = [1000000000.0 for i in range(31)]
		c[1] = 'g'
		d[1] = 0
		q = deque()
		q.append(1)
		while len(q) > 0:
			v = q.popleft()
			for u in e[v]:
				if c[u] == 'w':
					c[u] = 'g'
					d[u] = d[v] + 1
					q.append(u)
			c[v] = 'b'
		return d[30]


class Solution:

	def minThrow(self, N, arr):

		def get_neighbours(i):
			neighbours = []
			for val in range(i + 1, i + 7):
				if val > 30:
					continue
				neighbours.append(ladder_snake_map.get(val, val))
			return neighbours
		ladder_snake_map = {}
		i = 0
		while i < 2 * N:
			ladder_snake_map[arr[i]] = arr[i + 1]
			i += 2
		visited = [False for i in range(30)]
		q = [(ladder_snake_map.get(1, 1), 0)]
		while q:
			(val, tries) = q.pop(0)
			if val == 30:
				return tries
			for neighbour in get_neighbours(val):
				if visited[neighbour - 1]:
					continue
				visited[neighbour - 1] = True
				q.append((neighbour, tries + 1))
		return -1


import collections

class Solution:

	def minThrow(self, N, arr):
		jumps = {}
		for i in range(0, len(arr), 2):
			jumps[arr[i]] = arr[i + 1]
		print(jumps)
		visited = set()
		q = collections.deque([1])
		visited.add(1)
		turns = 0
		while q:
			for k in range(len(q)):
				n = q.popleft()
				if n == 30:
					return turns
				for d in range(1, 7):
					if d + n == 30:
						return turns + 1
					if d + n > 30 or d + n in visited:
						continue
					if d + n in jumps:
						q.append(jumps[d + n])
						visited.add(d + n)
						visited.add(jumps[d + n])
					else:
						q.append(d + n)
						visited.add(d + n)
			print(q)
			turns += 1
		return turns

class Solution:

	def minThrow(self, N, arr):
		min_paths = {1: [1]}
		dists = {1: 0}
		jumps = {}
		end_node = 30
		for i in range(0, len(arr), 2):
			jumps[arr[i]] = arr[i + 1]
		q = collections.deque([1])
		while q:
			curr_pos = q.popleft()
			neighb_nodes = []
			for d in range(1, 7):
				if d + curr_pos in jumps.keys():
					neighb_nodes.append(jumps[d + curr_pos])
				elif d + curr_pos <= 30:
					neighb_nodes.append(d + curr_pos)
			for node in neighb_nodes:
				if node not in min_paths:
					q.append(node)
					min_paths[node] = min_paths[curr_pos] + [node]
					dists[node] = dists[curr_pos] + 1
					if node == end_node:
						return dists[node]


import collections

class Solution:

	def minThrow(self, N, arr):
		jumps = {}
		for i in range(0, len(arr), 2):
			jumps[arr[i]] = arr[i + 1]
		visited = set()
		q = collections.deque([1])
		visited.add(1)
		turns = 0
		while q:
			for k in range(len(q)):
				n = q.popleft()
				if n == 30:
					return turns
				for d in range(1, 7):
					if d + n == 30:
						return turns + 1
					if d + n > 30 or d + n in visited:
						continue
					if d + n in jumps:
						q.append(jumps[d + n])
						visited.add(d + n)
						visited.add(jumps[d + n])
					else:
						q.append(d + n)
						visited.add(d + n)
			turns += 1
		return turns


class Solution:

	def minThrow(self, N, arr):
		d = {}
		for i in range(0, N * 2, 2):
			d[arr[i]] = arr[i + 1]
		st = []
		st.append([1, 0])
		while True:
			t = st.pop(0)
			for i in range(1, 7):
				if t[0] + i <= 30:
					if t[0] + i == 30:
						return t[1] + 1
					if t[0] + i in d:
						st.append([d[t[0] + i], t[1] + 1])
					else:
						st.append([t[0] + i, t[1] + 1])


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		END = 30
		snake = set()
		ladder = dict()
		visited = [False] * (END + 1)
		for i in range(N):
			if arr[2 * i] < arr[2 * i + 1]:
				ladder[arr[2 * i]] = arr[2 * i + 1]
			else:
				snake.add(arr[2 * i])
		dq = deque([1])
		visited[1] = True
		steps = 0
		while dq:
			for _ in range(len(dq)):
				node = dq.popleft()
				if node == END:
					return steps
				neighbors = []
				for i in range(node + 1, node + 7):
					if i in ladder:
						neighbors.append(ladder[i])
					elif i in snake:
						continue
					elif i <= END:
						neighbors.append(i)
				for nei in neighbors:
					if not visited[nei]:
						visited[nei] = True
						dq.append(nei)
			steps += 1
		return -1


from collections import deque

class Solution:

	def minThrow(self, n, arr):
		ladder = [-1] * 31
		for i in range(0, 2 * n, 2):
			ladder[arr[i]] = arr[i + 1]
		q = deque()
		q.append([1, 0])
		ladder[1] = 0
		while len(q) > 0:
			front = q.popleft()
			if front[0] == 30:
				return front[1]
			for i in range(1, 7):
				indx = front[0] + i
				if indx <= 30 and ladder[indx] != 0:
					if ladder[indx] == -1:
						q.append([indx, front[1] + 1])
						ladder[indx] = 0
					elif ladder[indx] < indx:
						ladder[indx] = 0
					else:
						q.append([ladder[indx], front[1] + 1])
						ladder[ladder[indx]] = 0
						ladder[indx] = 0
		return -1


class Solution:

	def minThrow(self, N, arr):
		d = {}
		for i in range(N):
			d[arr[2 * i]] = arr[2 * i + 1]
		vis = [False for i in range(31)]
		vis[1] = 1
		q = []
		q.append((1, 0))
		while q:
			(curr, cnt) = q.pop(0)
			if curr == 30:
				return cnt
			for i in range(curr + 1, curr + 7):
				if i < 31 and (not vis[i]):
					vis[i] = 1
					new = i
					if d.get(i):
						new = d.get(i)
					q.append((new, cnt + 1))
		return -1


class Solution:

	def minThrow(self, N, arr):
		vis = [False] * 37
		d = dict()
		i = 0
		while i < 2 * N - 1:
			d[arr[i]] = arr[i + 1]
			i += 2
		q = list()
		q.append((1, 0))
		vis[1] = 1
		while q:
			node = q[0][0]
			dist = q[0][1]
			q.pop(0)
			if node == 30:
				return dist
			for i in range(node + 1, node + 7):
				if not vis[i]:
					vis[i] = 1
					if i in d.keys():
						nNode = d[i]
					else:
						nNode = i
					q.append((nNode, dist + 1))
		return -1


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

class Solution:

	def minThrow(self, N, arr):
		from sys import maxsize
		ans = [maxsize]
		dp = {}
		vis = [0 for i in range(31)]
		d = {}
		for i in range(N):
			(sp, ep) = (arr[2 * i], arr[2 * i + 1])
			d[sp] = ep

		def f(cn):
			if vis[cn] == 1:
				return maxsize
			if cn in dp:
				return dp[cn]
			if cn == 30:
				return 0
			if cn in d:
				temp = f(d[cn])
				dp[cn] = temp
				return temp
			vis[cn] = 1
			temp = maxsize
			for i in range(1, 7):
				nn = cn + i
				if nn > 30:
					continue
				temp = min(temp, f(nn) + 1)
			dp[cn] = temp
			vis[cn] = 0
			return temp
		return f(1)


class Solution:

	def minThrow(self, N, arr):
		d = {}
		for i in range(0, N * 2, 2):
			d[arr[i]] = arr[i + 1]
		que = [[1, 0]]
		vis = [False] * 40
		vis[0] = True
		vis[1] = True
		while que:
			(ans, steps) = que.pop(0)
			if ans == 30:
				return steps
			for i in range(1, 7):
				res = ans + i
				if vis[res] == False:
					vis[res] = True
					if res in d:
						que.append([d[res], steps + 1])
					else:
						que.append([res, steps + 1])
		return -1


from collections import defaultdict

class Solution:

	def minThrow(self, N, arr):
		edges = defaultdict(lambda : 100)
		for i in range(0, N * 2, 2):
			edges[arr[i + 1]] = min(arr[i], edges[arr[i + 1]])
		d = defaultdict(lambda : float('inf'))
		d[1] = 0
		for i in range(2, 31):
			d[i] = min(d[i - 1], d[i - 2], d[i - 3], d[i - 4], d[i - 5], d[i - 6], d[edges[i]] - 1) + 1
		return d[30]


class Solution:

	def minThrow(self, N, arr):
		dic = {}
		for i in range(len(arr) // 2):
			dic[arr[2 * i]] = arr[2 * i + 1]
		a = [0]
		for i in range(1, 31):
			if i in dic:
				a.append(dic[i])
			else:
				a.append(i)
		vis = [0 for _ in range(32)]
		q = [1]
		cnt = 0
		vis[1] = 1
		res = 0
		while len(q) > 0:
			if res != 0:
				return res
			tq = []
			cnt += 1
			for k in q:
				for jj in range(k + 1, k + 7):
					if jj > 30:
						continue
					j = a[jj]
					if vis[j] != 1:
						vis[j] = 1
						tq.append(j)
					if j == 30:
						res = cnt
						break
			q = tq
		return res


class Solution:

	def minThrow(self, N, arr):
		from collections import deque
		Map = {}
		for i in range(0, len(arr), 2):
			Map[arr[i]] = arr[i + 1]
		Queue = deque()
		Queue.append([1, 0])
		Visited = [0] * 31
		Visited[1] = 1
		Ans = 30
		while len(Queue) != 0:
			top = Queue.popleft()
			(cell, step) = (top[0], top[1])
			if cell == 30:
				return step
			for roll in range(1, 7):
				nextcell = cell + roll
				if nextcell <= 30 and Visited[nextcell] == 0:
					Visited[nextcell] = 1
					if nextcell in Map:
						nextcell = Map[nextcell]
						if Visited[nextcell] == 0:
							Visited[nextcell] = 1
					Queue.append([nextcell, step + 1])
		return 0


class Solution:

	def minThrow(self, N, arr):
		visited = [-1 for i in range(31)]
		snl = dict()
		for i in range(0, len(arr) - 1, 2):
			snl[arr[i]] = arr[i + 1]
		q = [(1, 0)]
		visited[1] = 1
		while q:
			(curr, diceRolled) = q.pop(0)
			if curr == 30:
				return diceRolled
			for i in range(1, 7):
				newPos = curr + i
				if newPos > 30:
					break
				if newPos in snl:
					newPos = snl[newPos]
				if visited[newPos] == -1:
					q.append((newPos, diceRolled + 1))
					visited[newPos] = 1
		return -1


class Solution:

	def minThrow(self, N, arr):
		tele = [i for i in range(31)]
		visited = [False for i in range(31)]
		visited[1] = True
		for i in range(0, 2 * N, 2):
			tele[arr[i]] = arr[i + 1]
		q = [1]
		dice = 0
		p = 0
		s = 1
		while p < len(q):
			node = q[p]
			if node == 30:
				return dice
			p += 1
			s -= 1
			for i in range(1, 7):
				if node + i <= 30 and visited[tele[node + i]] == False:
					q.append(tele[node + i])
					visited[tele[node + i]] = True
			if s == 0:
				dice += 1
				s = len(q) - p
		return -1


class Solution:

	def minThrow(self, N, arr):
		teleport = [i for i in range(31)]
		visited = [False for i in range(31)]
		visited[1] = True
		for i in range(N):
			teleport[arr[2 * i]] = arr[2 * i + 1]
		q = [1]
		ptr = 0
		level = 0
		while ptr < len(q):
			c = len(q) - ptr
			for _ in range(c):
				top = q[ptr]
				if top == 30:
					return level
				ptr += 1
				for i in range(1, 7):
					if top + i <= 30 and (not visited[teleport[top + i]]):
						q.append(teleport[top + i])
						visited[teleport[top + i]] = True
			level += 1


class Solution:

	def minThrow(self, N, arr):
		from collections import deque
		mapDict = {arr[2 * i]: arr[2 * i + 1] for i in range(len(arr) // 2)}
		q = deque()
		q.append(1)
		turns = 0
		finish = False
		while True:
			for i in range(len(q)):
				position = q.popleft()
				for i in range(1, 7):
					if position + i == 30:
						finish = True
						break
					elif i + position in mapDict:
						q.append(mapDict[i + position])
					else:
						q.append(position + i)
			turns += 1
			if finish:
				break
		return turns


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		pipes = {}
		for i in range(0, len(arr), 2):
			pipes[arr[i]] = arr[i + 1]
		que = deque([1])
		step = 0
		while que:
			for _ in range(len(que)):
				curr = que.popleft()
				if curr == 30:
					return step
				for j in range(1, 7):
					nbr = curr + j
					if nbr in pipes:
						que.append(pipes[nbr])
					else:
						que.append(nbr)
			step += 1
		return 0


class Solution:

	def minThrow(self, n, arr):
		N = 30
		dp = [1 << 32] * (N + 1)
		dp[0] = 0
		dp[1] = 0
		ladder = {}
		snake = {}
		for i in range(0, 2 * n, 2):
			if arr[i] < arr[i + 1]:
				if arr[i + 1] in ladder:
					if arr[ladder[arr[i + 1]] - 1] > arr[i]:
						ladder[arr[i + 1]] = i + 1
				else:
					ladder[arr[i + 1]] = i + 1
			else:
				snake[arr[i]] = i
		for i in range(2, N + 1):
			if i in snake:
				continue
			elif i in ladder:
				dp[i] = dp[arr[ladder[i] - 1]]
			for j in range(1, 7):
				if i - j >= 1:
					dp[i] = min(dp[i], dp[i - j] + 1)
		return dp[-1]


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		d = {}
		i = 0
		while i < len(arr):
			d[arr[i]] = arr[i + 1]
			i += 2
		q = deque([1])
		moves = 1
		visited = set([1])
		while q:
			for _ in range(len(q)):
				currPos = q.popleft()
				for move in range(1, 7):
					if currPos + move >= 30:
						return moves
					if currPos + move not in visited:
						visited.add(currPos + move)
						if currPos + move in d:
							q.append(d[currPos + move])
						else:
							q.append(currPos + move)
			moves += 1
		return moves


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		dic = dict()
		for i in range(0, 2 * N, 2):
			dic[arr[i]] = arr[i + 1]
		dis = [1e+18] * 31
		q = deque()
		q.append(1)
		dis[1] = 0
		while q:
			nod = q.popleft()
			for i in range(1, 7):
				d = nod + i
				if d <= 30:
					if d in dic:
						d = dic[d]
					if dis[d] > dis[nod] + 1:
						dis[d] = dis[nod] + 1
						q.append(d)
				else:
					break
		return dis[-1]


from queue import Queue

class Graph:

	def __init__(self, board_size: tuple, snakes_and_ladders: list):
		(row, column) = board_size
		self.vertices = row * column
		self.edges = {}
		lookup = {}
		for i in range(0, len(snakes_and_ladders), 2):
			lookup[snakes_and_ladders[i]] = snakes_and_ladders[i + 1]
		for i in range(1, self.vertices):
			if i not in lookup:
				self.edges[i] = [lookup[x] if x in lookup else x for x in range(i + 1, i + 7) if x <= 30]

def shortest_path(graph: Graph, starting_vertex: int, end_vertex: int) -> int:
	shortest_distances = [-1 for i in range(graph.vertices + 1)]
	shortest_distances[starting_vertex] = 0
	queue = Queue()
	queue.put(starting_vertex)
	while not queue.empty():
		vertex = queue.get()
		if vertex in graph.edges:
			for edge in graph.edges[vertex]:
				if shortest_distances[edge] == -1:
					queue.put(edge)
					shortest_distances[edge] = shortest_distances[vertex] + 1
	return shortest_distances[end_vertex]

class Solution:

	def minThrow(self, N, arr):
		g = Graph((5, 6), arr)
		return shortest_path(g, 1, 30)


from queue import Queue

class Solution:

	def minThrow(self, N, arr):
		q = Queue()
		visited = [0] * 31
		q.put((1, 0))
		while not q.empty():
			(pos, dist) = q.get()
			if pos >= 30:
				return dist
			for j in range(1, 7):
				(x, x_dist) = (pos + j, dist + 1)
				for i in range(N):
					if arr[2 * i] == x:
						x_pos = arr[2 * i + 1]
						q.put((x_pos, x_dist))
			q.put((x, dist + 1))
		return 0


import collections

class Solution:

	def minThrow(self, n, arr):
		flat = [-1 for i in range(30)]
		for i in range(0, len(arr), 2):
			flat[arr[i] - 1] = arr[i + 1] - 1
		q = collections.deque()
		best = [None] * 30
		q.append(0)
		best[0] = 0
		while len(q) > 0:
			current = q.popleft()
			for i in range(1, 7):
				nx = current + i
				if flat[nx] != -1:
					nx = flat[nx]
				if nx == 29:
					return best[current] + 1
				if best[nx] is None:
					q.append(nx)
					best[nx] = best[current] + 1
		return -1


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		mp = {}
		for i in range(0, len(arr), 2):
			mp[arr[i]] = arr[i + 1]
		queue = deque()
		queue.append([1, 0])
		ans = float('inf')
		while queue:
			(a, c) = queue.popleft()
			if a >= 30:
				return c
			for n in [1, 2, 3, 4, 5, 6]:
				k = a + n
				if k in mp:
					k = mp[k]
				queue.append([k, c + 1])
		return -1


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		moves = [-1 for i in range(35)]
		vis = [False for i in range(35)]
		i = 0
		while i < 2 * N:
			moves[arr[i]] = arr[i + 1]
			i += 2
		q = deque()
		q.append([1, 0])
		vis[1] = True
		while len(q) > 0:
			cur = q.popleft()
			node = cur[0]
			throws = cur[1]
			if node == 30:
				return throws
			for nnode in range(node + 1, node + 7):
				if nnode > 30:
					break
				add = [0] * 2
				if vis[nnode] == False:
					vis[nnode] = True
					add[1] = throws + 1
					if moves[nnode] != -1:
						add[0] = moves[nnode]
					else:
						add[0] = nnode
					q.append(add)
		return -1


SIZE = 5 * 6

class Solution:

	def BFS(self, adj, start):
		visited = set()
		visited.add(start)
		q = []
		q.append((0, start))
		while q:
			(cost, curr) = q.pop(0)
			if curr == SIZE - 1:
				return cost
			for v in adj[curr]:
				if v not in visited:
					visited.add(v)
					q.append((cost + 1, v))
		return -1

	def minThrow(self, N, arr):
		sn_ld = {}
		for i in range(0, 2 * N, 2):
			sn_ld[arr[i] - 1] = arr[i + 1] - 1
		adj = [[] for i in range(SIZE)]
		for i in range(SIZE):
			for j in range(i + 1, i + 7):
				if j < SIZE:
					if j in sn_ld:
						adj[i].append(sn_ld[j])
					else:
						adj[i].append(j)
		return self.BFS(adj, 0)


class Solution:

	def minThrow(self, N, arr):
		dp = [float('inf')] * 31
		(dp[0], dp[1]) = (0, 0)
		h = {}
		for i in range(0, 2 * N, 2):
			startPoint = arr[i]
			endPoint = arr[i + 1]
			h[startPoint] = endPoint
		for i in range(2, 31):
			if i in h:
				if h[i] < i:
					continue
			for j in range(1, 7):
				if i - j > 0 and dp[i - j] != float('inf'):
					dp[i] = min(dp[i], dp[i - j] + 1)
			if i in h:
				if h[i] > i:
					dp[h[i]] = min(dp[h[i]], dp[i])
		return dp[-1]


from queue import Queue

class Solution:

	def minThrow(self, N, arr):
		d = {}
		i = 0
		while i < len(arr):
			d[arr[i]] = arr[i + 1]
			i += 2
		obj = Queue()
		obj.put([0, 1])
		visited = [-1 for _ in range(31)]
		visited[1] = 0
		while not obj.empty():
			(cost, node) = obj.get()
			if node == 30:
				return cost
			else:
				for i in range(1, min(30 - node + 1, 7)):
					to = node + i
					if to in d:
						to = d[to]
					if visited[to] == -1 or visited[to] > cost + 1:
						visited[to] = cost + 1
						obj.put([cost + 1, to])
		return -1


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		snakes = {}
		ladder = {}
		for i in range(0, N * 2, 2):
			if arr[i] < arr[i + 1]:
				ladder[arr[i]] = arr[i + 1]
			else:
				snakes[arr[i]] = arr[i + 1]
		q = deque()
		q.append((1, 0))
		while len(q) > 0:
			(number, steps) = q.popleft()
			for i in range(1, 7):
				nnumber = number + i
				if nnumber == 30:
					return steps + 1
				if nnumber in ladder:
					q.append((ladder[nnumber], steps + 1))
				elif nnumber in snakes:
					q.append((snakes[nnumber], steps + 1))
				else:
					q.append((nnumber, steps + 1))


from collections import defaultdict, deque

class Solution:

	def minThrow(self, n, arr):
		graph = defaultdict(list)
		mapping = dict()
		k = 0
		while k < 2 * n:
			mapping[arr[k]] = arr[k + 1]
			k += 2
		for i in range(1, 30):
			for j in range(1, 7):
				if i + j <= 30:
					if i + j in mapping:
						graph[i].append(mapping[i + j])
					else:
						graph[i].append(i + j)
		visited = [False for i in range(31)]
		queue = deque()
		queue.append((1, 0))
		visited[1] = True
		while queue:
			(u, chance) = queue.popleft()
			for neighbour in graph[u]:
				if neighbour == 30:
					return chance + 1
				if visited[neighbour] == False:
					queue.append((neighbour, chance + 1))
					visited[neighbour] = True


import math

class Solution:

	def minThrow(self, N, arr):

		def dfs(s, visited, h):
			if s >= 30:
				return 0
			elif s > 30:
				return math.inf
			if visited[s] != -1:
				return visited[s]
			mn = math.inf
			for i in range(1, 7):
				m = s + i
				if m in h:
					m = h[m]
				mn = min(mn, 1 + dfs(m, visited, h))
			visited[s] = mn
			return visited[s]

		def solve(N, arr):
			hash_map = {}
			for i in range(0, 2 * N, 2):
				if arr[i] < arr[i + 1]:
					hash_map[arr[i]] = arr[i + 1]
			visited = [-1 for i in range(31)]
			return dfs(1, visited, hash_map)
		return solve(N, arr)


class Solution:

	def minThrow(self, n, arr):
		q = []
		q.append([1, 0])
		m = dict()
		for i in range(n):
			m[arr[2 * i]] = arr[2 * i + 1]
		while len(q) != 0:
			cur = q.pop(0)
			throws = cur[1]
			node = cur[0]
			if node == 30:
				return throws
			for i in range(1, 7):
				newnode = node + i
				if newnode <= 30:
					if newnode in m:
						q.append([m[newnode], throws + 1])
					else:
						q.append([newnode, throws + 1])
		return -1


class Solution:

	def minThrow(self, n, arr):
		index = [-1] * 31
		visit = [-1] * 31
		for i in range(0, len(arr), 2):
			index[arr[i]] = arr[i + 1]
		que = []
		que.append(1)
		count = 0
		while len(que) > 0:
			l = len(que)
			while l > 0:
				l -= 1
				el = que.pop(0)
				if visit[el] != -1:
					continue
				else:
					visit[el] = 1
				if el == 30:
					return count
				for i in range(el + 1, el + 7, 1):
					if i > 30:
						break
					if index[i] == -1:
						que.append(i)
					else:
						que.append(index[i])
			count += 1
		return count


class Solution:

	def minThrow(self, N, arr):
		endCell = 30
		moves = [-1 for _ in range(endCell)]
		for start in range(0, 2 * N, 2):
			s = arr[start]
			e = arr[start + 1]
			moves[s - 1] = e - 1
		queue = [(0, 0)]
		totalHop = 0
		while len(queue):
			(start, hop) = queue.pop(0)
			if start == endCell - 1:
				totalHop = hop
				break
			v = start + 1
			while v <= start + 6 and v < 30:
				newV = v if moves[v] == -1 else moves[v]
				queue.append((newV, hop + 1))
				v += 1
		return totalHop


import heapq

class Solution:

	def minThrow(self, n, a):
		l = [[-1] * 6 for i in range(5)]

		def getcoard(x):
			r = x // 6
			c = x % 6
			if r % 2 != 0:
				c = 5 - c
			return (r, c)

		def formboard():
			for i in range(0, 2 * n, 2):
				(p, q) = getcoard(a[i] - 1)
				l[p][q] = a[i + 1]
		formboard()
		heap = [(0, 1)]
		v = set()
		while heap:
			(c, x) = heapq.heappop(heap)
			if x == 30:
				return c
			for i in range(x + 1, x + 7, 1):
				if i in v:
					continue
				if i > 30:
					break
				(p, q) = getcoard(i - 1)
				if l[p][q] != -1:
					heapq.heappush(heap, (c + 1, l[p][q]))
				else:
					heapq.heappush(heap, (c + 1, i))
		return -1


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		t = 5 * 6
		s_l = {}
		for i in range(0, 2 * N, 2):
			s_l[arr[i] - 1] = arr[i + 1] - 1
		q = deque()
		q.append([0, 0])
		visit = set()
		while q:
			(pos, moves) = q.popleft()
			for i in range(1, 7):
				next_pos = pos + i
				if next_pos < t:
					if next_pos in s_l:
						next_pos = s_l[next_pos]
					if next_pos not in visit:
						if next_pos == t - 1:
							return moves + 1
						visit.add(next_pos)
						q.append([next_pos, moves + 1])
		return -1


class Solution:

	def minThrow(self, N, arr):
		g = [-1] * 31
		for i in range(0, 2 * N, 2):
			g[arr[i]] = arr[i + 1]
		q = []
		q.append(1)
		cnt = 0
		vis = [False for i in range(31)]
		vis[1] = True
		while q:
			size = len(q)
			for i in range(size):
				front = q.pop(0)
				if front == 30:
					return cnt
				for dice in range(1, 7):
					if dice + front > 30:
						break
					pos = dice + front
					if vis[pos]:
						continue
					else:
						vis[pos] = True
					if g[pos] == -1:
						q.append(pos)
					else:
						q.append(g[pos])
			cnt += 1
		return -1


class Solution:

	def minThrow(self, N, arr):
		d = {}
		for i in range(N):
			d[arr[2 * i]] = arr[2 * i + 1]
		q = []
		v = set()
		v.add(1)
		q.append((1, 0))
		while q:
			(a, b) = q.pop(0)
			if a == 30:
				return b
			for i in range(1, 7):
				if a + i <= 30:
					if a + i in d and d[a + i] not in v:
						q.append((d[a + i], b + 1))
						v.add(d[a + i])
					elif a + i not in d and a + i not in v:
						q.append((a + i, b + 1))
						v.add(a + i)
		return -1


from collections import deque

class Solution:

	def minThrow(self, N, move):
		parent = [-1] * 35
		for i in range(0, N * 2, 2):
			parent[move[i]] = move[i + 1]
		q = deque()
		q.append((1, 0))
		visited = set()
		visited.add(1)
		while q:
			(node, dis) = q.popleft()
			if node == 30:
				return dis
			for i in range(node + 1, node + 7):
				if i < 31:
					if i not in visited:
						visited.add(i)
						if parent[i] == -1:
							q.append((i, dis + 1))
						elif parent[i] != -1:
							q.append((parent[i], dis + 1))
				else:
					break
		return -1


class Solution:

	def minThrow(self, N, arr):
		vis = [0] * 31
		d = [i for i in range(31)]
		for i in range(0, len(arr), 2):
			d[arr[i]] = arr[i + 1]
		q = [[1, 0]]
		while q:
			(x, y) = q.pop(0)
			if x == 30:
				return y
			for i in range(1, 7):
				if 0 <= x + i < 31 and vis[d[x + i]] == 0:
					vis[d[x + i]] = 1
					q.append([d[x + i], y + 1])
		return -1


class Solution:

	def minThrow(self, N, arr):
		snakes = {}
		ladder = {}
		for i in range(0, 2 * N, 2):
			if arr[i] < arr[i + 1]:
				ladder[arr[i]] = arr[i + 1]
			else:
				snakes[arr[i]] = arr[i + 1]
		queue = [(1, 0)]
		while len(queue):
			(pos, move) = queue.pop(0)
			if pos == 30:
				return move
			for i in range(1, 7):
				temp = pos + i
				if temp <= 30:
					if temp in snakes:
						continue
					if temp in ladder:
						queue.append((ladder[temp], move + 1))
					else:
						queue.append((temp, move + 1))
		return -1


class Solution:

	def minThrow(self, N, arr):
		pos = 1
		moves = 0
		vect = []
		for i in range(0, N * 2, 2):
			vect.append([arr[i], arr[i + 1]])
		vect.sort()
		for i in range(1, N):
			if vect[i - 1][1] > vect[i][0] and vect[i][0] < vect[i][1] and (vect[i][1] > vect[i - 1][1]):
				vect[i - 1][1] = vect[i - 1][0] - 1
		while pos < 30:
			mi = pos + 6
			pm = [1, 2, 3, 4, 5, 6]
			i = 0
			while i < N:
				if vect[i][0] <= pos + 6 and vect[i][0] >= pos:
					if vect[i][0] < vect[i][1]:
						mi = max(mi, vect[i][1])
					elif pos + 6 >= vect[i][0]:
						pm.remove(vect[i][0] - pos)
						if len(pm):
							if mi <= pos + 6:
								mi = pos + pm[-1]
						else:
							assert 0
				i += 1
			pos = mi
			moves += 1
		return moves


class Solution:

	def minThrow(self, N, arr):
		mp = {}
		for i in range(N):
			start = arr[2 * i]
			end = arr[2 * i + 1]
			mp[start] = end
		q = []
		visited = [False] * 31
		q.append([1, 0])
		visited[1] = True
		while q:
			(curr_cell, steps) = q.pop(0)
			if curr_cell == 30:
				return steps
			for dice in range(1, 7):
				new_cell = curr_cell + dice
				if new_cell in mp:
					new_cell = mp[new_cell]
				if new_cell <= 30 and (not visited[new_cell]):
					q.append([new_cell, steps + 1])
					visited[new_cell] = True
		return -1


class Solution:

	def minThrow(self, N, arr):
		queue = [1]
		l = {}
		s = {}
		visited = set()
		visited.add(1)
		ans = 0
		i = 0
		while i < N:
			l[arr[i]] = arr[i + 1]
			i += 2
		j = N
		while j <= 2 * N - 2:
			s[arr[j]] = arr[j + 1]
			j += 2
		while len(queue) != 0:
			for _ in range(len(queue)):
				ele = queue.pop(0)
				for i in range(1, 7):
					temp = ele + i
					if temp == 30:
						return ans + 1
					if temp not in visited:
						if temp in l:
							queue.append(l[temp])
							visited.add(l[temp])
						elif temp in s:
							queue.append(s[temp])
							visited.add(s[temp])
						else:
							queue.append(temp)
							visited.add(temp)
			ans += 1


def add_edge(graph, x, y):
	graph[x].append(y)

def single_source_shortest_path(graph, start):
	visited = {start: 0}
	q = [start]
	while len(q):
		node = q.pop(0)
		for n in graph[node]:
			if n not in visited:
				q.append(n)
				visited[n] = visited[node] + 1
	return visited

class Solution:

	def minThrow(self, N, arr):
		n = 30
		graph = [[] for i in range(n + 1)]
		board = [0 for i in range(n + 10)]
		for i in range(0, len(arr), 2):
			board[arr[i]] = arr[i + 1] - arr[i]
		for i in range(n + 1):
			for dice in range(1, 7):
				j = i + dice
				j += board[j]
				if j <= n:
					add_edge(graph, i, j)
		paths = single_source_shortest_path(graph, 1)
		return paths[n]


class Solution:

	def minThrow(self, N, arr):
		l = []
		s = arr
		s1 = []
		for i in range(0, len(s), 2):
			if s[i] < s[i + 1]:
				l.append(s[i])
				l.append(s[i + 1])
			else:
				s1.append(s[i])
		for i in range(0, len(l), 2):
			if i < len(l) - 2 and l[i + 1] > l[i + 2]:
				if l[i + 1] - l[i] < l[i + 3] - l[i + 2]:
					l[i] = -1
					l[i + 1] = -1
		l1 = []
		for i in l:
			if i != -1:
				l1.append(i)
		l = l1
		ans = 1
		count = 0
		while ans < 30:
			maxvalue = ans
			for i in range(0, len(l), 2):
				if l[i] <= ans + 6 and l[i] >= ans:
					maxvalue = max(maxvalue, l[i + 1])
			if maxvalue < ans + 6:
				for k in range(6, -1, -1):
					if ans + k not in s1:
						maxvalue = ans + k
						break
			count += 1
			ans = maxvalue
		return count


from collections import defaultdict

class Solution:

	def minThrow(self, N, arr):
		adj = {}
		index = 0
		while index < len(arr) - 1:
			adj[arr[index]] = arr[index + 1]
			index += 2
		queue = [1]
		count = 0
		while len(queue) > 0:
			count += 1
			for _ in range(len(queue)):
				currCell = queue.pop(0)
				for throw in range(1, 7):
					newCell = currCell + throw
					if newCell in adj:
						newCell = adj[newCell]
					if newCell >= 30:
						return count
					queue.append(newCell)
		return -1


class Solution:

	def minThrow(self, N, arr):
		visited = [0] * 30
		hash = {}
		for i in range(0, len(arr) - 1, 2):
			hash[arr[i] - 1] = arr[i + 1] - 1
		q = [(0, 0)]
		visited[0] = 1
		while q:
			cur = q.pop(0)
			throw = cur[0]
			start = cur[1]
			if start == 29:
				return throw
			for i in range(6):
				new_pos = start + i + 1
				if new_pos <= 29:
					if new_pos in hash:
						new_pos = hash[new_pos]
					if visited[new_pos] == 0:
						visited[new_pos] = 1
						q.append((throw + 1, new_pos))
		return -1


class Pos:

	def __init__(self, pos, dist):
		self.pos = pos
		self.dist = dist

class Solution:

	def findNextMove(self, arr, pos):
		while pos in arr and arr.index(pos) % 2 == 0:
			pos_index = arr.index(pos)
			pos = arr[pos_index + 1]
		return pos

	def minThrow(self, N, arr):
		if N == 0:
			return -1
		q = [(1, 0)]
		visited = [0] * 31
		visited[1] = 1
		while len(q):
			(current_node, curr_dist) = q.pop(0)
			if current_node == 30:
				return curr_dist
			for i in range(1, min(current_node + 7, 31)):
				if not visited[i]:
					neig_pos = self.findNextMove(arr, i)
					visited[neig_pos] = 1
					q.append((neig_pos, curr_dist + 1))
		return -1


import collections

class Solution:

	def minThrow(self, N, arr):
		vis = [0] * 31
		for i in range(1, len(arr), 2):
			if arr[i] > arr[i - 1]:
				vis[arr[i - 1]] = arr[i]
			elif arr[i] < arr[i - 1]:
				vis[arr[i - 1]] = arr[i] - arr[i - 1]
		q = collections.deque()
		q.append([1, 0])
		seen = set()
		while q:
			(idx, moves) = q.popleft()
			for i in range(1, 7):
				next_idx = idx + i
				if vis[next_idx] != 0:
					next_idx = vis[next_idx]
				if next_idx == 30:
					return moves + 1
				if next_idx not in seen:
					seen.add(next_idx)
					q.append([next_idx, moves + 1])


class Solution:

	def minThrow(self, N, arr):
		conn = [100 for times in range(0, 31)]
		for i in range(0, 2 * N, 2):
			conn[arr[i]] = arr[i + 1]
		visited = [-1 for times in range(0, 31)]
		visited[1] = 0
		q = [1]
		(front, back) = (0, 0)
		while front <= back:
			val = q[front]
			front += 1
			for i in range(1, 7):
				if val + i <= 30:
					if visited[val + i] == -1 and conn[val + i] >= val + i:
						if conn[val + i] == 100:
							q.append(val + i)
							visited[val + i] = visited[val] + 1
							back += 1
						else:
							q.append(conn[val + i])
							visited[val + i] = visited[val] + 1
							visited[conn[val + i]] = visited[val + i]
							back += 1
		return visited[30]


from collections import deque

class Solution:

	def minThrow(self, N, arr):

		def dfs(s, visited, h):
			if s >= 30:
				return 0
			elif s > 30:
				return 10000000000.0
			if visited[s] != -1:
				return visited[s]
			mn = 10000000000.0
			for i in range(1, 7):
				m = s + i
				if m in h:
					m = h[m]
				mn = min(mn, 1 + dfs(m, visited, h))
			visited[s] = mn
			return visited[s]
		hash_map = {}
		for i in range(0, 2 * N, 2):
			if arr[i] < arr[i + 1]:
				hash_map[arr[i]] = arr[i + 1]
		visited = [-1 for i in range(31)]
		return dfs(1, visited, hash_map)
		return solve(N, arr)


class Solution:

	def minThrow(self, n, arr, dp=None, i=0, poss=None):
		if dp == None:
			dp = [-1 for i in range(30)]
			poss = [-1 for i in range(29)]
			dp[29] = 0
			for j in range(0, n):
				poss[arr[2 * j] - 1] = arr[2 * j + 1] - 1
		if i > 29:
			return float('inf')
		if dp[i] != -1:
			return dp[i]
		if poss[i] == -1:
			minm = float('inf')
			for j in range(6):
				if i + j + 1 < 30:
					minm = min(1 + self.minThrow(n, arr, dp, i + j + 1, poss), minm)
			dp[i] = minm
		elif poss[i] < i:
			dp[i] = 31
		else:
			dp[i] = self.minThrow(n, arr, dp, poss[i], poss)
		return dp[i]


class Solution:

	def minThrow(self, n, array):
		(ladder, snakes, idx) = ({}, {}, 0)
		while idx < len(array):
			if array[idx] < array[idx + 1]:
				ladder[array[idx]] = array[idx + 1]
			else:
				snakes[array[idx]] = array[idx + 1]
			idx += 2
		return self.breadthFirstSearch(snakes, ladder, 30)

	def breadthFirstSearch(self, snakes, ladder, target):
		(queue, visited, minSteps) = ([(1, 0)], {}, float('inf'))
		while queue:
			(current, steps) = queue.pop(0)
			if current == target:
				minSteps = min(minSteps, steps)
				continue
			visited[current] = True
			for change in (1, 2, 3, 4, 5, 6):
				new = current + change
				if new <= 30:
					if new in ladder:
						new = ladder[new]
					elif new in snakes:
						new = snakes[new]
					if new not in visited:
						queue.append((new, steps + 1))
						visited[new] = True
		return minSteps


from collections import deque

class Solution:

	def minThrow(self, N, arr):
		vis = set()
		q = deque()
		q.append((1, 0))
		di = {arr[i]: arr[i + 1] for i in range(0, N * 2, 2)}
		while q:
			(v, t) = q.popleft()
			vis.add(v)
			if v == 30:
				return t
			neis = self.get_neighbors(arr, di, v)
			if neis:
				for x in neis:
					if x not in vis:
						q.append((x, 1 + t))

	def get_neighbors(self, arr, di, v):
		neis = []
		for i in range(1, 7):
			n = v + i
			neis.append(n)
			if n in di:
				neis.append(di[n])
		return neis


class Solution:

	def minThrow(self, n, a):
		l = [[0] * 6 for i in range(5)]

		def getcoard(x):
			r = x // 6
			c = x % 6
			if r % 2 != 0:
				c = 5 - c
			return (r, c)

		def formboard():
			for i in range(0, 2 * n, 2):
				(x, y) = getcoard(a[i] - 1)
				l[x][y] = a[i + 1]
		formboard()
		v = set()
		queue = [(1, 0)]
		v.add(1)
		while queue:
			z = queue.pop(0)
			if z[0] == 30:
				return z[1]
			for j in range(z[0] + 1, z[0] + 7):
				if j in v:
					continue
				if j > 30:
					break
				(x, y) = getcoard(j - 1)
				if l[x][y] == 0:
					queue.append((j, z[1] + 1))
				else:
					queue.append((l[x][y], z[1] + 1))
				v.add(j)


from collections import defaultdict

class Solution:

	def minThrow(self, N, arr):
		snakeladder = defaultdict(lambda : 0)
		for i in range(0, 2 * N, 2):
			snakeladder[arr[i]] = arr[i + 1]
		visited = defaultdict(lambda : False)
		q = []
		q.append(1)
		visited[1] = True
		moves = 0
		while q:
			size = len(q)
			moves += 1
			while size:
				front = q.pop(0)
				for i in range(1, 6 + 1):
					neighbrs = front + i
					if neighbrs == 30:
						return moves
					if not visited[neighbrs] and neighbrs < 30:
						if snakeladder[neighbrs] != 0:
							q.append(snakeladder[neighbrs])
							visited[snakeladder[neighbrs]] = True
						else:
							q.append(neighbrs)
							visited[neighbrs] = True
				size -= 1
		return moves


class Solution:

	def minThrow(self, N, arr):
		a1 = {}
		a2 = {}
		for i in range(1, len(arr), 2):
			if arr[i] > arr[i - 1]:
				if arr[i] not in a1:
					a1[arr[i]] = arr[i - 1]
				else:
					a1[arr[i]] = min(a1[arr[i]], arr[i - 1])
			else:
				a2[arr[i - 1]] = arr[i]
		d = [float('inf')] * 31
		d[1] = 0
		for i in range(2, 31):
			c = 1
			e = float('inf')
			while i - c >= 1 and c <= 6:
				if i - c not in a2:
					e = min(e, d[i - c] + 1)
				c += 1
			if i in a1:
				e = min(e, d[a1[i]])
			d[i] = e
		return d[-1]


from heapq import *

class Solution:

	def shortestDistance(self, adj, ladder_dict):
		dp = [1000000000] * 31
		visited = [0] * 31
		bag = []
		dp[1] = 0
		heappush(bag, [0, 1])
		while bag:
			(d, n) = heappop(bag)
			for ch in adj[n]:
				if visited[ch] == 0:
					if d + 1 < dp[ch]:
						if ladder_dict.get(n) == ch:
							dp[ch] = d
						else:
							dp[ch] = d + 1
						visited[ch] = 1
						heappush(bag, [dp[ch], ch])
		return dp[30]

	def minThrow(self, N, arr):
		adj = []
		ladder_dict = {}
		for i in range(31):
			ladder_dict[i] = -1
			adj.append([])
		for i in range(1, 31):
			for j in range(i + 1, i + 7):
				if j <= 30:
					adj[i].append(j)
		for i in range(0, len(arr), 2):
			ladder_dict[arr[i]] = arr[i + 1]
			adj[arr[i]].append(arr[i + 1])
		return self.shortestDistance(adj, ladder_dict)