#!/usr/bin/python3
import re, sys

class automata:
    def __init__(self):
        self.states = []
        self.rules = []
        self.current = '0'

    def datainp(self, rls, wins):
        for rule in rls:
            self.rules += [(rule.split(' '))]
        self.win_states = wins
        self.states = [row[2] for row in self.rules]

    def check(self):
        k = [row[::2] for row in self.rules]
        if [x for x in k if k.count(x) > 1]:
            return True
        return False

    def play(self, word):
        for l in list(word)[:-1]:
            if (l not in self.states):
                self.current = 'something'
                break
            res = 0
            for rule in self.rules:
                if (rule[0] == self.current) and (rule[2] == l):
                    self.current = rule[1]
                    res = 1
                    break
            if (res == 0):
                self.current = 'something'
                break
        if (self.current in self.win_states):
            print ('YES ' + word[:-1])
        else:
            print ('NO ' + word[:-1])
        self.current = '0'

def search_rules(inp):
    return re.findall(r'[0-9]* [0-9]* [a-z]', inp)
def search_states(inp):
    return re.findall(r'([0-9]+)\n', inp)


file = ''
for line in sys.stdin:
    file = file + line
z = automata()
z.datainp(search_rules(file), search_states(file))
if (z.check()):
    print('NONDETERMINISTIC')
else:
    data = open(sys.argv[1], 'r')
    for line in data:
        z.play(line)