# Function to construct an adjacency list representation of a graph
def construct_adjacency_list(n, edges):
    # Initialize an empty adjacency list with 'n' empty sets
    adj = [set() for i in range(n)]

    # Iterate through the 'edges' list and add edges to the adjacency list
    for v1, v2 in edges:
        adj[v1].add(v2)
        adj[v2].add(v1)

    # Return the constructed adjacency list
    return adj

# Function to find the minimum height trees in a graph
def min_height_trees(n, edges):
    # If there are 1 or 2 nodes, return them as the minimum height trees
    if n <= 2:
        return [i for i in range(n)]

    # Construct the adjacency list for the graph
    adj = construct_adjacency_list(n, edges)

    # Initialize a list to store the leaves of the graph
    leaves = [i for i in range(n) if len(adj[i]) == 1]

    # Initialize a variable to keep track of remaining nodes
    rem_nodes = n

    # Iterate until there are only 1 or 2 nodes left
    while rem_nodes > 2:
        # Decrement the count of remaining nodes by the number of leaves
        rem_nodes -= len(leaves)
        
        # Initialize a temporary list to store new leaves
        temp_leaves = []

        # Iterate through the current leaves
        while leaves:
            # Pop a leaf node
            leaf = leaves.pop()

            # Get its neighbor
            neighbor = adj[leaf].pop()

            # Remove the link from the neighbor back to the leaf
            adj[neighbor].remove(leaf)

            # If the neighbor becomes a new leaf, add it to 'temp_leaves'
            if len(adj[neighbor]) == 1:
                temp_leaves.append(neighbor)

        # Update 'leaves' with the new leaves found in this iteration
        leaves = temp_leaves

    # Return the remaining nodes as the minimum height trees
    return leaves

# Driver code
def main():
    input1 = [1, 2, 3, 4, 6]
    input2 = [[], [[0, 1]], [[0, 1], [1, 2]], [[1, 0], [1, 2], [2, 3]], [[0, 1], [0, 2], [0, 3], [0, 4], [4, 5]]]

    for i in range(len(input1)):
        print(str(i + 1) + ".\t", "n:", input1[i], 
              "\n\t edges:", input2[i],
              "\n\n\t Root nodes that minimize the height:", min_height_trees(input1[i], input2[i]))

        print("-" * 100)

if __name__ == '__main__':
    main()