{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"Two familiar concepts in object oriented programming are the is-a and has-a relationships. Given two classes \u003cb\u003eA\u003c/b\u003e and \u003cb\u003eB\u003c/b\u003e, we say that A is-a B if A is a subclass of B; we say A has-a B if one of the fields of A is of type B.\nFor example, we could imagine an object-oriented language (call it ICPC++) with code like that in Figure\nE.1, where the class Day is-a Time, the class Appointment is both a DateBook and a Reminder, and\nclass Appointment has-a Day.\u003cbr\u003e\u003cbr\u003e\n\n$\\texttt{class Day extends Time}$ \u003cbr\u003e\n$\\{$\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;$\\texttt{...}$\u003cbr\u003e\n$\\}$\u003cbr\u003e\n\u003cbr\u003e\n\n$\\texttt{class Appointment extends Datebook, Reminder}$\u003cbr\u003e\n$\\{$\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;$\\texttt{private Day date;}$\u003cbr\u003e\n\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;$\\texttt{...}$\u003cbr\u003e\n$\\}$\u003cbr\u003e\n\n\u003cbr\u003e\nThese two relationships are transitive. For example if A is-a B and B is-a C then it follows that A is-a C.\nThis holds as well if we change all the is-a’s in the last sentence to has-a’s. It also works with combinations\nof is-a’s and has-a’s: in the example above, $\\texttt{Appointment}$ has-a $\\texttt{Time}$, since it has-a $\\texttt{Day}$ and $\\texttt{Day}$ is-a\n$\\texttt{Time}$. Similarly, if class $\\texttt{DateBook}$ has-a $\\texttt{Year}$ then $\\texttt{Appointment}$ has-a $\\texttt{Year}$, since $\\texttt{Appointment}$\nis-a $\\texttt{DateBook}$.\n\n\u003cbr\u003e\nIn this problem you will be given a set of is-a and has-a relationships and a set of queries of the form A\nis/has-a B. You must determine if each query is true or false."}},{"title":"Input","value":{"format":"HTML","content":"Input starts with two integers $n$ and $m$, $(1 ≤ n, m ≤ 10 000)$, where $n$ specifies the number of given is-a\nand has-a relationships and $m$ specifies the number of queries. The next $n$ lines each contain one given\nrelationship in the form $c_1$ $r$ $c_2$ where $c_1$ and $c_2$ are single-word class names, and $r$ is either the string “is-a”\nor “has-a”. Following this are $m$ queries, one per line, using the same format. There will be at most $500$\ndistinct class names in the $n + m$ lines, and all class names in the last $m$ lines will appear at least once in the\ninitial $n$ lines. All is-a and has-a relationships between the given classes can be deduced from the $n$ given\nrelationships. Is-a relationships can not be circular (apart from the trivial identity “x is-a x”)."}},{"title":"Output","value":{"format":"HTML","content":"For each query, display the query number (starting at one) and whether the query is true or false."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 5\nDay is-a Time\nAppointment is-a Datebook\nAppointment is-a Reminder\nAppointment has-a Day\nDatebook has-a Year\nDay is-a Time\nTime is-a Day\nAppointment has-a Time\nAppointment has-a Year\nDay is-a Day\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eQuery 1: true\nQuery 2: false\nQuery 3: true\nQuery 4: true\nQuery 5: true\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}