from collections import defaultdict

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 1: return [0]
        neighbors = defaultdict(list)
        degrees = defaultdict(int)
        for u, v in edges:
            neighbors[u].append(v)
            neighbors[v].append(u)
            degrees[u] += 1
            degrees[v] += 1

        # First find the leaves
        preLevel, unvisited = [], set(range(n))
        for i in range(n):
            if degrees[i] == 1: preLevel.append(i)

        while len(unvisited) > 2:
            thisLevel = []
            for u in preLevel:
                unvisited.remove(u)
                for v in neighbors[u]:
                    if v in unvisited:
                        degrees[v] -= 1
                        if degrees[v] == 1: thisLevel += [v]
            preLevel = thisLevel

        return preLevel

    # Memory Limit Exceeded
    # def findMinHeightTrees(self, n, edges):
    #     """
    #     :type n: int
    #     :type edges: List[List[int]]
    #     :rtype: List[int]
    #     """
    #     if len(edges)==0: return [0]
    #     if n==1 and len(edges)==1: return [edges[0][0]]
    #     if n==2 and len(edges)==1: return edges[0]
    #
    #     vertices = defaultdict(set)
    #     for edge in edges:
    #         vertices[edge[0]].add(edge[1])
    #         vertices[edge[1]].add(edge[0])
    #
    #     leaves, starter = list(), None
    #     for node, neighbors in vertices.iteritems():
    #         if len(neighbors)==1:
    #             leaves.append(node)
    #             starter = node
    #
    #     # First pass x->y
    #     farthest, max_height = None, -sys.maxint-1
    #     stack, visited = [(starter, 0)], set()
    #     while len(stack)>0:
    #         tmp = stack.pop()
    #         curr, height = tmp[0], tmp[1]
    #         if curr not in visited:
    #             visited.add(curr)
    #             if height>max_height:
    #                 farthest = curr
    #                 max_height = height
    #             for neighbor in vertices[curr]:
    #                 stack.append((neighbor, height+1))
    #     starter = farthest
    #
    #
    #     # Second pass y->z (longest path in the tree)
    #     longest_path = None
    #     farthest, max_height = None, -sys.maxint-1
    #     stack, visited = [(starter, 0, [starter])], set()
    #     while len(stack)>0:
    #         tmp = stack.pop()
    #         curr, height, path = tmp[0], tmp[1], tmp[2]
    #         if curr not in visited:
    #             visited.add(curr)
    #             if height>max_height:
    #                 farthest = curr
    #                 max_height = height
    #                 longest_path = path
    #             for neighbor in vertices[curr]:
    #                 stack.append((neighbor, height+1, path+[neighbor]))
    #
    #     length = len(longest_path)
    #     return [longest_path[length/2]] if length%2==1 else longest_path[(length/2)-1:(length/2)+1]
