Time Complexity: O(n)
Space Complexity: O(n) n total number of nodes

class Solution(object):
    def findSmallestRegion(self, regions, region1, region2):
        """
        :type regions: List[List[str]]
        :type region1: str
        :type region2: str
        :rtype: str
        """


        #Main idea: Simple version of topological sorting.
        #           The graph for this problem is a tree
        #  1). Construct graph using Hashmap. 
        #  2). Find lowest common ancestor of two nodes


        Parent = {}

        for List in regions:
            for i in range(1, len(List)):
                Parent[List[i]] = List[0]


        Ancestor = set([region1])


        while(region1 in Parent):
            region1 = Parent[region1]
            Ancestor.add(region1)

        while(region2 not in Ancestor):
            region2 = Parent[region2]

        return region2