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


class automata:
    # class variables init
    def __init__(self):
        # dictionary of connections between nodes
        self.graph = {}
        # list of accepting states
        self.accepting_states = []
        # list of current states
        self.state = ['0']
        # word variable
        self.word = ''

    # print for debug purposes
    def __repr__(self):
        return('%s\n\n%s\n\n%s\n\n' % (self.graph, self.accepting_states, self.state))

    # add node in open fst format
    def add_node(self, line):
        node = line.replace('\n', '').split(' ')
        if len(node) == 3:
            if node[0] in self.graph:
                # add value to existing node
                self.graph[node[0]].append({node[2]: node[1]})
            else:
                # create new node
                self.graph[node[0]] = [{node[2]: node[1]}]
        elif len(node) == 1:
            # add accepting state
            self.accepting_states.append(node[0])

    # check if string is accepted by automate
    def test_string(self, word):
        self.state = ['0']
        self.word = word.replace('\n', '')
        # for all values in word
        for i in self.word:
            # for all actual states
            result = []
            for q in self.state:
                # move state to its transition
                result = self.get_node_transition(q, i)
            # if the list is empty, return false
            if not self.state:
                return False
            # flatten list of states
            self.state = [item for sublist in result for item in sublist]
        # check if automata is in accepting state
        return self.check_if_accepted()

    # check if there is common part between states of automata and accepting states
    def check_if_accepted(self):
        return not set(self.state).isdisjoint(self.accepting_states)

    def get_node_transition(self, q, i):
        result = []
        # if the node exists
        try:
            # search through all its connections to find value
            for connections in self.graph[q]:
                for value in connections:
                    if value == i:
                        # append next node
                        result.append(connections[value])
        except KeyError:
            return result
        # return list of next nodes
        return result


auto = automata()

for line in sys.stdin:
    auto.add_node(line)

f = open(sys.argv[1], 'r')

for line in f:
    if auto.test_string(line):
        print("TRUE %s" % auto.word)
    else:
        print("FALSE %s" % auto.word)