题目描述

你是一名决斗者，渴望成为下一任剑术大师。你需要通过与对手决斗，直到你战胜了每一位对手。每个对手始终可以与你决斗，且对手之间不会互相决斗。

每位决斗者（包括你自己）至少掌握一种攻击和一种防御。世界上最多存在 $P$ 对攻击与防御，每一对中的第 $i$ 种防御只能克制第 $i$ 种攻击，第 $i$ 种攻击也只会被第 $i$ 种防御克制。可能存在某些攻击或防御没有任何决斗者掌握。你可以无限次使用自己掌握的任意攻击或防御，它们不会“用完”。

每场与对手的单独决斗规则如下：

• 作为剑术大师的候选人，你总是先攻击。你选择自己会的一种攻击。如果对手会相应的防御，则可以选择使用该防御。如果对手不会该防御，或者选择不使用，则无法防御。
• 然后，对手选择自己会的一种攻击。如果你会相应的防御，则可以选择使用该防御。如果你不会该防御，或者选择不使用，则无法防御。
• 如果你成功防御了对手的攻击，而对手没有防御你的攻击，则你赢得这场决斗！否则，你未能获胜，但你追求剑术大师之路可以继续。

你可以进行任意多场决斗，包括与同一对手多次决斗，无论之前的结果如何。你不需要提前安排所有决斗的顺序，可以根据之前的结果决定下一步。只要你至少战胜过每一位对手一次，你就成为了剑术大师！

你有极强的学习能力。每场决斗结束后，无论胜负，你都可以将对手在该场决斗中使用的攻击和防御（如果有）加入到你自己的已知攻击/防御集合中。（注意，如果对手在对你攻击时使用了你不熟悉的防御，你在本场决斗中无法学会，因此不能在本场对对手的攻击使用该防御。）只有你拥有这个优势；对手们掌握的攻击和防御永远不会变化。

此外，在你战胜某位对手后，在下一场决斗之前，该对手会将他们所掌握而你尚未掌握的所有攻击和防御全部教给你。（他们输给你后，希望你最终能成为剑术大师，这样对他们更有面子！）

你知道每位对手掌握哪些攻击和防御。如果你做出最优选择，是否可以保证最终成为剑术大师，无论对手如何选择？

输入格式

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。

每组数据开头一行包含两个整数 $N$ 和 $P$，分别表示决斗者（包括你自己）的数量，以及世界上最多存在的攻击/防御对数。

接下来有 $N$ 组，每组包含三行，描述每位决斗者（第一个为你自己）：

1. 一行包含两个整数 $Attacks_i$ 和 $Defenses_i$，分别表示第 $i$ 位决斗者已知的攻击数和防御数。
2. 一行包含 $Attacks_i$ 个不同的递增整数 $A_{ij}$，表示第 $i$ 位决斗者已知的攻击编号。
3. 一行包含 $Defenses_i$ 个不同的递增整数 $D_{ij}$，表示第 $i$ 位决斗者已知的防御编号。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为 YES 或 NO，表示你是否可以保证最终成为剑术大师。

输入输出样例 #1

输入 #1

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

输出 #1

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

说明/提示

样例解释

注意，最后四个样例不会出现在测试集 1 中。

样例 1 中，只要你的对手一直选择防御 1 并使用攻击 1，你就无法获胜。无法保证对手会选择攻击 2 或不使用防御 1，因此无法保证你能成为剑术大师。

样例 2 中，你会攻击 1 和防御 2，唯一的对手会攻击 2 和防御 1。你可以采用如下策略保证获胜：

• 首先，你必须选择攻击 1；对手可能用防御 1 防御。然后，对手只能选择攻击 2，你应选择防御 2。
  • 如果对手没有防御，你获胜，成为剑术大师。
  • 否则，你未能获胜，但你学会了攻击 2 和防御 1。然后再次与该对手决斗，这次你选择攻击 2，对手无法防御。对手仍然只能选择攻击 2，你用防御 2。你获胜，成为剑术大师。

样例 3 中，若对手始终选择攻击 4，你永远无法防御，因为没人会防御 4。因此你无法成为剑术大师。注意，可能存在世界上有攻击或防御，但无人掌握。

样例 4 中，有一位对手掌握所有防御，因此你无法保证战胜他（除非他“好心”不防御）。

样例 5 的一种必胜策略如下：

1. 与第一个对手决斗。你只能选择攻击 1，对方无法防御。假设对方选择攻击 2（如果选择攻击 3，也有类似策略）。你无法防御，未能获胜，但你学会了攻击 2。
2. 与第三个对手决斗，使用攻击 2 和防御 4，必胜。你学会攻击 4（虽然不会用到）和防御 1、3。
3. 与第二个对手决斗，使用攻击 2。你一定能学会防御 2：要么对手用它防御你，要么不用你直接获胜（并学会他所有攻击和防御）。
4. 再次与第一个对手决斗，选择攻击 1。此时无论对方用哪种攻击，你都能防御，获胜。你学会攻击 3。
5. 如之前未战胜第二个对手，再次与其决斗，使用攻击 3。

数据范围

• $1 \leq T \leq 100$。
• $2 \leq N \leq 1000$。
• $1 \leq P \leq 1000$。
• $1 \leq Attacks_i \leq P$，对所有 $i$。
• $1 \leq Defenses_i \leq P$，对所有 $i$。
• $1 \leq A_{ij} < A_{i(j+1)} \leq P$，对所有 $i$ 和 $j$。
• $1 \leq D_{ij} < D_{i(j+1)} \leq P$，对所有 $i$ 和 $j$。
• 所有 $Attacks_i$ 与 $Defenses_i$ 之和不超过 $50000$。