Is-A? Has-A? Who Knows-A?

Object oriented programming has two familiar relationships: is-a and has-a. Given two classes A and B, A is-a B if A is a subclass of B, and A has-a B if one of the fields of A is of type B. Imagine an object oriented language called ICPC++ with code like the figure below. There the class Day is-a Time, the class Appointment is both a Datebook and a Reminder, and the class Appointment has-a Day.

class Day extends Time        class Appointment extends Datebook, Reminder
{                             {
    ...                           private Day date;
}                                 ...
                              }

Figure 1: Two ICPC++ classes.

Both relationships are transitive. If A is-a B and B is-a C, then A is-a C. The same holds when every is-a in the previous sentence becomes a has-a. It also works for combinations of the two. In the example above Appointment has-a Time, because Appointment has-a Day and Day is-a Time. Likewise, if Datebook has-a Year, then Appointment has-a Year, because Appointment is-a Datebook.

In short, relationships are deduced by these four rules.

• If A is-a B and B is-a C, then A is-a C.
• If A has-a B and B has-a C, then A has-a C.
• If A is-a B and B has-a C, then A has-a C.
• If A has-a B and B is-a C, then A has-a C.

In addition, x is-a x is true for every class x.

You are given a set of is-a and has-a relationships together with a set of queries of the form A is-a B or A has-a B. Decide whether each query is true or false.

The first line has two integers $n$ and $m$ ($1 \le n, m \le 10000$), where $n$ is the number of given relationships and $m$ is the number of queries.

Each of the next $n$ lines holds one relationship in the form c1 r c2, where c1 and c2 are single-word class names without spaces, compared case sensitively, and r is either the string is-a or the string has-a. Each of the following $m$ lines holds one query in the same form.

At most $500$ distinct class names appear in the $n + m$ lines, and every class name in the last $m$ lines appears at least once in the first $n$ lines. All is-a and has-a relationships between the given classes follow from the $n$ given relationships. Is-a relationships are never circular, apart from the trivial identity x is-a x, which is always true. Has-a relationships may be circular, in which case x has-a x can be true.

For each query print one line with the query number and the answer. Query numbers start at one. If query $i$ is true, print Query i: true, otherwise print Query i: false. For example, a false second query prints the line Query 2: false.