ある秘密結社が1899年に一人の創設者によって設立されました。その創設者の名前は秘密にされています。その後、結社のメンバーは既存メンバーの推薦によって加入してきました。
結社への加入には、厳格に守られている一つのユニークなルールがあります。推薦は一人以上の既存メンバーによって行われますが、同じメンバーのグループが推薦できる新しいメンバーは一人だけです。例えば、あるメンバーが既存メンバーのグループ $\{A, B, C\}$ による推薦で加入を許可された場合、同じ推薦者グループによって他の人が加入を許可されることはありません。しかし、グループ $\{A, B\}$ が別の新しいメンバーを推薦することは全く問題ありません。$\{A, B\}$ は $\{A, B, C\}$ の部分集合ですが、これらは異なる集合です。一貫性を保つため、創設者の推薦者グループは空集合とみなされます。
この秘密結社に関する調査を通じて、結社のメンバーシップ構造の一部を表すいくつかの情報の断片を入手しました。各情報の断片は以下の形式のいずれかをとります。ここで、$a, b, c$ は結社の特定のメンバーを指す整数です。
recommend a b
メンバー $a$ が、メンバー $b$ の加入を推薦したグループに属していることを意味します。
not-recommend a b
メンバー $a$ が、メンバー $b$ の加入を推薦したグループに属していないことを意味します。
intersection a b c
メンバー $a$ の推薦者グループが、$b$ の推薦者グループと $c$ の推薦者グループの共通部分（積集合）であることを意味します。言い換えれば、$a$ を推薦したすべての人は $b$ と $c$ の両方を推薦しており、かつ $b$ と $c$ の両方を推薦したすべての人は $a$ を推薦しているということです。
同じ整数が複数回現れる場合は同じメンバーを指しますが、異なるステートメント間であっても同様です。一方で、異なる整数が同じ人物の別名である可能性もあります（一つのステートメント内であっても同様です）。
入手した情報は断片的である可能性があります。つまり、一部のメンバーの推薦関係が不明であったり、どのステートメントにも言及されていないメンバーが存在したりする可能性があります。
情報源が必ずしも信頼できるとは限らないため、誤った情報が含まれている可能性があります。これらのステートメントが整合しているか、つまり、これらすべてのステートメントと矛盾しない推薦関係が存在し得るかどうかを判定してください。
入力
入力には1つ以上のテストケースが含まれます。入力の最初の行にはテストケースの数 $t$ ($1 \le t \le 3000$) が含まれます。続いて $t$ 個のテストケースが以下の形式で記述されます。
$n$ $s_1$ $\vdots$ $s_n$
最初の行にはステートメントの数 $n$ ($1 \le n \le 3000$) が与えられます。続く $n$ 行の各行は “recommend a b”、“not-recommend a b”、または “intersection a b c” のいずれかの形式であり、$a, b, c$ はすべて $1$ 以上 $3n$ 以下の整数です。
すべてのテストケースにおける $n$ の合計は 3000 を超えません。
出力
各テストケースについて、ステートメントで記述された状況が可能であれば yes を、そうでなければ no を1行に出力してください。
入出力例
入力 1
3 2 recommend 1 2 not-recommend 1 2 2 recommend 1 2 recommend 2 1 3 intersection 1 2 2 recommend 1 3 not-recommend 2 3
出力 1
no no no
入力 2
4 3 intersection 3 2 1 recommend 3 2 not-recommend 3 1 4 intersection 1 2 3 recommend 4 2 recommend 4 3 not-recommend 4 1 3 intersection 3 2 1 recommend 2 5 intersection 3 4 5 5 recommend 1 3 not-recommend 2 3 not-recommend 3 2 not-recommend 1 2 not-recommend 2 1
出力 2
yes no yes yes
注記
サンプル入力 1 では、すべてのテストケースが不可能な状況を記述しています。
- 最初のテストケースでは、2つのステートメントが明らかに矛盾しています。
- 2番目のテストケースでは、最初のステートメントはメンバー 1 が先に結社に加入し、その後メンバー 2 が加入したことを示唆しています（そうでなければメンバー 1 がメンバー 2 を推薦できないため）。しかし、2番目のステートメントは逆の順序を示唆しています。両方を満たすことは不可能です。
- 3番目のテストケースでは、最初のステートメントは本質的にメンバー 1 の推薦者集合とメンバー 2 の推薦者集合が同一であることを述べています。同じ推薦者集合を持つメンバーは存在しないため、1 と 2 は同じメンバーを指していなければなりません。その場合、2番目と3番目のステートメントが矛盾します。
サンプル入力 2 の最初のテストケースは可能です。考えられるシナリオは多数あります。一例として、メンバー 3 が実際には創設者であり、メンバー 2 が $\{3\}$ の推薦で加入し、メンバー 1 が $\{2\}$ の推薦で加入したという状況が挙げられます。
サンプル入力 2 の最後のテストケースも可能です。結社のすべてのメンバーが情報の中で言及されている必要はないことに注意してください。結社には少なくとも 4 人のメンバーが存在する必要があります。