import random


def recursive_back_tracker_maze(bm_edges, full_mesh=False):
    """trace a perfect maze through bm_edges
    input:
        bm_edges: list of BMEdges - needs to be pre-sorted on index
        full_mesh: does bm_edges include the whole mesh
    output:
        maze_path: list of BMEdges
        maze_verts: list of BMVerts
    """
    stack = []
    maze_path = []
    maze_verts = []
    # start at a random vert in maze
    start_vert = random.choice(bm_edges).verts[0]
    stack.append(start_vert)
    maze_verts.append(start_vert)
    while len(stack) > 0:
        current_vert = stack[-1]
        if full_mesh:
            # faster if we don't check edge is in bm_edges
            free_link_edges = [
                e
                for e in current_vert.link_edges
                if (e.other_vert(current_vert) not in maze_verts)
            ]
        else:
            # check edge in bm_edge
            free_link_edges = [
                e
                for e in current_vert.link_edges
                if (e in bm_edges)
                and (e.other_vert(current_vert) not in maze_verts)
            ]

        if len(free_link_edges) == 0:
            stack.pop()
        else:
            link_edge = random.choice(free_link_edges)
            maze_path.append(link_edge)
            new_vert = link_edge.other_vert(current_vert)
            stack.append(new_vert)
            maze_verts.append(new_vert)

    return maze_path, maze_verts