P14690 [ICPC 2025 Yokohama R] Membership Structure of a Secret Society

A secret society with an undisclosed name was established in the year 1899 by a single founder, whose name is also kept secret. Subsequent members have joined the society through recommendations of existing members. One unique rule for joining the society has been strictly enforced: Recommendations can be made by one or more existing members, but the same member group can recommend only one new member. For example, if a member was allowed to join upon the recommendation by a group of existing members $\{A, B, C\}$, no other persons can be allowed by the same recommender group. It is perfectly acceptable, however, for a group $\{A, B\}$ to recommend another new member. Although the set $\{A, B\}$ is a subset of $\{A, B, C\}$, they are distinct sets. For consistency, the group of recommenders of the founder is considered to be the empty set. Through investigation of this secret society, you have obtained several information fragments representing some part of the membership structure of the society. Each information fragment takes one of the following forms of statements, in which the symbols $a$, $b$ and $c$ are integers designating certain members of the society. - **recommend** $a$ $b$ meaning that the member $a$ belongs to the group that recommended the member $b$ to join. - **not-recommend** $a$ $b$ meaning that the member $a$ does **not** belong to the group that recommended the member $b$ to join. - **intersection** $a$ $b$ $c$ meaning that the group of the recommenders of the member $a$ is the set intersection of recommender group of $b$ and that of $c$. In other words, all of those who recommended $a$ also recommended both $b$ and $c$, and all of those who recommended both $b$ and $c$ also recommended $a$. Two or more occurrences of the same integer mean the same member, even in different statements. On the other hand, two or more different integers may be aliases of the same person, even in a single statement. The obtained information may be partial, that is, the recommendations of some members may be missing, and, moreover, there may be some members not mentioned in any of the statements. As the information sources are not necessarily reliable, some false information might have crept in. You would like to know whether these statements are consistent, that is, whether there can be a recommendation relationship consistent with all of these statements.

The input contains one or more test cases. The first line of the input contains an integer $t$ ($1 \le t \le 3000$), which is the number of test cases. The descriptions of the $t$ test cases follow, each in the following format. $$ n $$ $$ s_1 $$ $$ \vdots $$ $$ s_n $$ The first line contains a single integer $n$, the number of statements ($1 \le n \le 3000$). Each of the following $n$ lines is in either of the formats "recommend $a$ $b$", "not-recommend $a$ $b$", or "intersection $a$ $b$ $c$", with all of $a$, $b$, and $c$ being integers between 1 and $3n$, inclusive. The sum of $n$'s over all the test cases does not exceed 3000.

For each test case, output $yes$ in one line if the situation described in the statements is possible, and output $no$, otherwise.