#!/usr/bin/python3
import sys
import re
transitions = {}
accepting = []
for line in sys.stdin:
    if re.search("^\d+\s\d+\s[a-z]$", line):
        accept = re.split("\s", line)
        if not transitions.get(str(accept[2])):
            transitions[str(accept[2])] = [str(accept[0]), str(accept[1])]
        else :
            transitions[str(accept[2])].append(str(accept[0]))
            transitions[str(accept[2])].append(str(accept[1]))
    elif re.search("^\d+$", line):
        accepting.append(int(line.replace('\n','')))

def gotostate(currentState, char):
    trans = transitions.get(char)
    if trans:
        for i in range(0, len(trans), 2):
            if int(trans[i]) == currentState:
                return int(trans[i+1])
    return None

def iscorrect(word):
    state = 0
    for char in word:
        state = gotostate(state, char)
        if state == None:
            return False
    for i in accepting:
        if i == state:
            return True
    return False

file = open(sys.argv[1])
for line in file:
    word = line.replace('\n','')
    if iscorrect(word):
        print("TRUE", word)
    else:
        print("FALSE", word)