class Node():
    def __init__(self, char):
        self.char = char
        self.children = dict()
        self.end = False

def noPrefix(words):
    trie = Node("")
    for i in range(len(words)):
        word = words[i]
        head = trie
        for i in range(len(word)):
            char = word[i]
            new_head = head.children.get(char)
            if new_head:
                if i == len(word) -1 or new_head.end:
                    print("BAD SET")
                    print(word)
                    exit()
                head = new_head
            else:
                head.children[char] = Node(char)
                head = head.children[char]
                if i == len(word) -1:
                    head.end = True
    print("GOOD SET")

	TrieNode root = new TrieNode();
        
        for(String word : words){
            TrieNode curr = root;
            boolean nodeAdded = false;
						
            for(int j=0; j<word.length(); j++){
                if(curr.isWord){
			//Found prefix in the tree
                    System.out.println("BAD SET");
                    System.out.println(word);
                    return;
                } 
								
		if(!curr.children.containsKey(word.charAt(j))){
                    curr.children.put(word.charAt(j), new TrieNode());
                    nodeAdded = true;
                }
                curr = curr.children.get(word.charAt(j));
            }
            curr.isWord = true;
            if(!nodeAdded){
		//No new node added means the word is a prefix
                System.out.println("BAD SET");
                System.out.println(word);
                return;
            }
        }
        System.out.println("GOOD SET");

// if any prefix existing on this path
bool checkPrefix(string& word, TrieNode* node){
    TrieNode* current = node;
    for(char ch:word){
        ch -= 'a';
        if(!current->children[ch]) break;
        current = current->children[ch];
        if(current->isEnd) return true;
    }
    return false;
}
// if the current string is a prefix of other string
bool isPrefix(string& word, TrieNode* node){
    TrieNode* current = node;
    for(char ch:word){
        ch -= 'a';
        if(!current->children[ch]) return false;
        current = current->children[ch];
    }
    
    for(auto& next:current->children){
        if(next) return true;
    }
    return false;
}