# Node of a prefix tree
class Node:
    def __init__(self):
        self.children = {}
        self.EndOfWord = False

# Trie data structure
class Trie:
    def __init__(self):
        '''
        Initialize a prefix tree with a root node.
        '''
        self.root = Node()
    
    def insert(self, word: str) -> bool:
        '''
        Insert a word into the prefix tree. Return True if any existing word is a prefix of currently inserted word. Else, return False.
        '''
        current = self.root
        flag = False
        for c in word:
            if c not in current.children:
                current.children[c] = Node()
            current = current.children[c]
            if current.EndOfWord and not flag:
                flag = True
        current.EndOfWord = True 
        return flag
    
    def startswith(self, prefix:str) -> bool:
        '''
        Does the prefix tree contain entries starting with a specific prefix?
        '''
        current = self.root
        for c in prefix:
            if c not in current.children:
                return False
            current = current.children[c]
        return True
        
def noPrefix(words: list[str]) -> None:
    '''
    Say N = len(words) and L = max word length.
    Space complexity: O(NL)
    Time complexity: O(NL)
    '''
    # Write your code here
    trie = Trie()
    for word in words:
        # Check if word exists in trie. If not, add word to trie.
        if trie.startswith(word):
            print('BAD SET', word, sep='\n')
            return None
        # When inserting word into trie, determine if any pre-added word in trie is a prefix of the newly added word.
        bool_flag = trie.insert(word)
        if bool_flag:
            print('BAD SET', word, sep='\n')
            return None
    print('GOOD SET')