class Graph:
    def __init__(self, ladders, snakes):
        self.adj_list = {i:set() for i in range(100)}
        special = {v-1:w-1 for v, w in ladders}
        special.update({v-1:w-1 for v, w in snakes})
        for i in range(99):
            for j in range(i+1, min(100, i+7)):
                if i in special:
                    continue
                self.adj_list[i].add(special.get(j, j))

            
    def bfs(self):
        q = deque([(0, 0)])
        vis = set([0])
        while q:
            dist, v = q.popleft()
            if v == 99:
                return dist
            for u in self.adj_list[v]:
                if not u in vis:
                    vis.add(u)
                    q.append((dist+1, u))
        return -1
                    
             
def quickestWayUp(ladders, snakes):
    g = Graph(ladders, snakes)
    return g.bfs()

def get_graph(ladders, snakes):
    graph = defaultdict(dict)
    for start, finish in ladders:
        graph[start][finish] = 0
    for start, finish in snakes:
        graph[start][finish] = 0
    return graph
    
def quickestWayUp(ladders, snakes):
    graph = get_graph(ladders, snakes)
    queue = deque()
    queue.append(1)
    costs = dict()
    visited = set([1])
    while queue:
        current_node = queue.popleft()
        neighbours = graph.get(current_node, {current_node + i: 1 for i in range(1, 7)})
        for neighbour in neighbours:
            if neighbour not in visited:
                costs[neighbour] = costs.get(current_node, 0) + neighbours[neighbour]
                visited.add(neighbour)
                queue.append(neighbour)
            if neighbour == 100:
                return costs[neighbour]
    return -1

    # BFS
    path={}
    for x in ladders+snakes:
        path[x[0]]=x[1]

    qu=[(1,0)]
    visit=set({1})
    while len(qu)>0:
        cur,step=qu.pop(0)
        if cur>=100:
            return step
        for i in range(1,7):
            if cur+i in path:
                nxt=path[cur+i]
            else:
                nxt=cur+i
            if nxt not in visit:
                visit.add(nxt)
                qu.append((nxt,step+1))
    
    return -1