package autom;

import java.io.*;
import java.util.*;
import java.util.ArrayList;
import java.util.logging.Level;
import java.util.logging.Logger;

public class Autom {

    ArrayList<String> slova;
    ArrayList<Hrana> hrany;
    ArrayList<Integer> cilove;
    int pocatek;


    class Hrana {
        int start;
        int cil;
        char c;

        public Hrana(int start, int cil, char c) {
            this.start = start;
            this.cil = cil;
            this.c = c;
        }


    }

      public void nactisl(File f) {
        try {
            BufferedReader br = null;
            br = new BufferedReader(new FileReader(f));
            String r = "";
            while ((r = br.readLine()) != null) {
                slova.add(r);
            }
            br.close();
        } catch (IOException ex) {
            Logger.getLogger(Autom.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

      public void nactia(File f) {
        try {
            BufferedReader br = null;
            br = new BufferedReader(new FileReader(f));
            String r = "";
            while ((r = br.readLine()) != null) {
                int ozn;
                String[] sl = r.split(" ");
                if (r.indexOf("*")!=-1) {
                    ozn = Integer.parseInt(sl[0].substring(1,sl[0].length()-1));
                    cilove.add(ozn);
                }
                else {
                    ozn = Integer.parseInt(sl[0].substring(1));
                }
                for(int i = 1; i<sl.length; i++) {
                    Hrana h = new Hrana(ozn, Integer.parseInt(sl[i].substring(2)), sl[i].charAt(0));
                    hrany.add(h);
                }
            }
            br.close();
        } catch (IOException ex) {
            Logger.getLogger(Autom.class.getName()).log(Level.SEVERE, null, ex);
        }
      }


    public Autom() {
        pocatek = 0;
        slova = new ArrayList<String>();
        cilove = new ArrayList<Integer>();
        hrany = new ArrayList<Hrana>();
        
    }


    private int exNext(int stav, char z) {
        for (Hrana h: hrany) {
            if (h.start == stav && h.c == z) return h.cil;
        }
        return -1;
    }

    boolean poc1(String s) {
        int stav = pocatek;
        int next;
        int i = 0;
        char z;
        while (i<s.length()) {
            z = s.charAt(i);
            if ((next = exNext(stav, z))==-1) return false;
            stav = next;
            i++;
        }
        if (cilove.contains(Integer.valueOf(stav))) return true;
        return false;
    }

    void pocitej() {
        for (String s :slova) {
            if (poc1(s)) System.out.println(s + " ANO");
            else System.out.println(s + " NE");
        }
    }


    public static void main(String[] args) {
        Autom autom = new Autom();
        autom.nactisl(new File("slova.in"));
        autom.nactia(new File("autom.in"));
        autom.pocitej();
    }

}