//simple trie data struct
class PrefixTrie
{
    public:
  
    unordered_map<char, PrefixTrie*> children;

};

void noPrefix(vector<string> words) {
    PrefixTrie root;
    
    //track if we are creating a new branch
    bool onNewBranch = true;
    
    for(string w : words)
    {
        PrefixTrie *next = &root;
        
        //add the word to the trie
        //if we encounter a node with no children then that means
        //we have seen the word before and its a prefix so bad set
        //also, if we add the entire word and never got to a new branch
        //then its a prefix of a word already in the tree
        for(char c : w)
        {         
            
            //if the node has children then its not a word we have seen   
            if(next->children.empty() && !onNewBranch)
            {
                cout << "BAD SET\n" << w << "\n";
                return;
            }
            //if the character doesnt exist in the children
            //then we are making a new branch
            if(next->children.find(c) == next->children.end())
            {
                next->children[c] = new PrefixTrie();
                onNewBranch = true;
            }
            
            next = next->children[c];
        }
        //if we got here but didnt make our own branch then we 
        //are part of another word'd branch and therefor a prefix
        if(!onNewBranch)
        {
            cout << "BAD SET\n" << w << "\n";
            return;  
        }
        
        onNewBranch = false;
    }
    
    cout << "GOOD SET\n";
}