def shortest_path(source, target):
    """
    Returns the shortest list of (movie_id, person_id) pairs
    that connect the source to the target.

    If no possible path, returns None.
    """
    lastNode = None
    result = []
    visited = set()
    visited_movies = set()
    # BFS
    root = Node(source, None, None)
    queue = QueueFrontier()
    visited.add(source)
    queue.add(root)
    while not queue.empty():
        # 获取当前用户id
        curNode = queue.remove()

        if target == curNode.state:
            lastNode=curNode
            break

        p_id = curNode.state
        # 获取参演电影
        movice_ids = people[p_id]["movies"]
        # 获取电影的star 逐个遍历
        for movie_id in movice_ids:
            if movie_id in visited_movies:
                continue
            stars = movies[movie_id]['stars']
            for star_id in stars:
                if star_id in visited:
                    continue
                pNode = Node(curNode.state, curNode.parent, curNode.action)
                node = Node(star_id, pNode, movie_id)
                visited.add(star_id)
                queue.add(node)
            visited_movies.add(movie_id)
    if lastNode is not None:
       while lastNode.parent is not None:
           m = lastNode.action
           p = lastNode.state
           result.insert(0,(m,p))
           lastNode=lastNode.parent
       return result
    else:
        return None