asdf

def bfs_tree(adj, start):
    n = len(adj)

    state = [("U") for i in range(n)]


    parent = [(None) for i in range(n)]
    Q = deque([start])
    state[start] = "D"
    Q.append(start)
    return bfs_loop(adj, Q, state, parent)



def bfs_loop(adj, Q, state, parent):
    while len(Q) > 0:
        u = Q.popleft()
        for vertex, _ in adj[u]:
            if state[vertex] == "U":
                state[vertex] = "D"
                parent[vertex] = u
                Q.append(vertex)
        state[u] = "P"
    return parent