题目描述

You are a duelist aspiring to become the next Swordmaster. You will work toward this title by dueling with opponents until you win against every opponent. Every opponent is always available for dueling, and opponents do not duel each other.

Each duelist (including you) knows at least one attack, and at least one defense. There are at most $P$ pairs of attacks and defenses in the world; the $i$-th defense only counters the $i$-th attack, and the $i$-th attack is only countered by the $i$-th defense. It is possible that there are attacks and/or defenses that no duelist knows. You can use any attack or defense that you know as many times as you like; they do not get "used up".

Here are the rules for each individual duel with an opponent:

• As the aspiring Swordmaster, you always get to attack first. You select an attack that you know. If the opponent knows the corresponding defense, they may choose to use it. If they do not know that defense, or they choose not to use it, then they do not defend.
• Then, the opponent selects an attack that they know. If you know the corresponding defense, you may choose to use it. If you do not know that defense, or you choose not to use it, then you do not defend.
• If you successfully defended and the opponent did not, you win the duel! Otherwise, you do not win, but your quest to become the Swordmaster can continue.

You can fight as many duels as you want, including multiple duels with the same opponent, regardless of the outcomes of any previous duels. You do not need to determine a complete schedule of duels in advance; you can base your next decision on what has already happened. Once you have won at least once against every opponent, you become the Swordmaster!

You are an especially quick learner. After each duel, regardless of the outcome of the duel, you can add the attack and the defense (if any) used by the opponent to your own set of known attacks/defenses. (Note that if an opponent uses an unfamiliar defense against you, you do not learn it during the duel itself, so you cannot use it against the opponent's attack in the same duel.) Only you have this advantage; the attacks and defenses known by your opponents never change.

Moreover, after you win against an opponent, and before your next duel, that opponent will teach you all of the attacks and defenses that they know and that you do not already know. (Once they have lost to you, it looks better for them if you eventually do become the Swordmaster!)

You know which attacks and defenses each opponent knows. If you make optimal choices, is it possible to guarantee that you will become the Swordmaster, regardless of what choices your opponents make?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

• Each case begins with one line with two integers $N$ and $P$: the number of duelists (including you), and the maximum number of attack/defense pairs in the world.
• Then, there are $N$ groups of three lines each. The $i$-th of these groups represents one of the duelists; in particular, the first of them represents you. Each group has the following structure:
  1. One line with two integers $Attacks_i$ and $Defenses_i$: the numbers of different attacks and defenses, respectively, known by the $i$-th duelist.
  2. One line with $Attacks_i$ different integers $A_{ij}$, sorted in increasing order: the identities of the attacks known by the $i$-th duelist.
  3. One line with $Defenses_i$ different integers $D_{ij}$, sorted in increasing order: the identities of the defenses known by the $i$-th duelist.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is YES if you can guarantee that you will become the Swordmaster (as described in the problem statement), or NO otherwise.

5
2 2
1 2
1
1 2
2 1
1 2
1
2 2
1 1
1
2
1 1
2
1
2 5
1 1
2
3
2 1
2 4
2
3 5
3 2
1 2 3
3 4
2 4
3 4
2 3 4 5
2 5
4 5
1 2 3 4 5
4 4
1 1
1
4
2 3
2 3
2 3 4
1 3
4
1 2 4
1 3
4
1 3 4

Case #1: NO
Case #2: YES
Case #3: NO
Case #4: NO
Case #5: YES

提示

Sample Explanation

Note that the last four sample cases would not appear in Test set 1.

In Sample Case #1, as long as your opponent keeps choosing defense 1 and attack 1, you cannot win the duel. There is no guarantee that your opponent will ever choose attack 2 or choose not to use defense 1, so it is not possible to guarantee that you will become the Swordmaster.

In Sample Case #2, you know attack 1 and defense 2, and your (only) opponent knows attack 2 and defense 1. The following strategy is guaranteed to make you the Swordmaster:

• In your first duel, you must choose attack 1; the opponent may defend with defense 1. Then, the opponent must choose attack 2; you should choose defense 2.
  • If the opponent did not defend, then you won and you are now the Swordmaster.
  • Otherwise, you do not win, but you learn attack 2 and defense 1 afterward. Then, start a second duel with that opponent. This time, choose attack 2; the opponent cannot defend against it. Once again, the opponent must choose attack 2; you should choose defense 2. You have won and you are now the Swordmaster.

In Sample Case #3, in your first duel, if your opponent always chooses attack 4, you will never be able to defend, since nobody knows the defense to that attack. So, there is no way for you to ever become the swordmaster. Note that there can be attacks and/or defenses that exist in the world, but are not known by any of the duelists in this problem.

In Sample Case #4, there is an opponent that knows every defense, so you cannot guarantee that you will ever win against them (they would have to be nice and not defend!)

Here is one guaranteed winning strategy for Sample Case #5:

1. Duel the first opponent. You must choose attack 1, and they cannot defend. We will proceed assuming that they choose attack 2. (If they choose attack 3, an isomorphic strategy will work.) You cannot defend, and you do not win the duel, but you learn attack 2.
2. Duel the third opponent, and use attack 2 and defense 4 for a guaranteed win. You learn attack 4 (which you will never use) and defenses 1 and 3.
3. Duel the second opponent, and use attack 2. You are guaranteed to learn defense 2: either the opponent will use it against you, or they will not use it and you will win (and learn all of their attacks and defenses).
4. Duel the first opponent again, and choose attack 1. Now, whichever attack they use, you can defend, and you win. You learn attack 3.
5. Duel the second opponent again, using attack 3, if you did not already win against them before.

Limits

• $1 \leq T \leq 100$.
• $2 \leq N \leq 1000$.
• $1 \leq P \leq 1000$.
• $1 \leq Attacks_i \leq P$, for all $i$.
• $1 \leq Defenses_i \leq P$, for all $i$.
• $1 \leq A_{ij} < A_{i(j+1)} \leq P$, for all $i$ and $j$.
• $1 \leq D_{ij} < D_{i(j+1)} \leq P$, for all $i$ and $j$.
• The sum of all $Attacks_i$ + the sum of all $Defenses_i$, over all $i$, does not exceed $50000$.

Test set 1 (10 Pts, Visible)

• $A_{i1} = 1$, for all $i$. (Attack 1 is known by all the duelists, including you.)
• $D_{i1} = 1$, for all $i$. (Defense 1 is known by all the duelists, including you.)

Test set 2 (38 Pts, Hidden)

• No extra restrictions.