[AdditionalFile6988.zip](file://AdditionalFile6988.zip?type=additional_file)

#6988. 「ICPC World Finals 2025」牧猫

标签: 传统 | 时间限制: 2000 ms | 内存限制: 2048 MiB |

题目描述

你正在巴库开一家猫咪咖啡馆，希望为所有坐在前窗的猫咪拍一张宣传照。不幸的是，让猫咪们听从你的指令是出了名的难题。但你有一个计划：你购买了 $m$ 株不同品种的猫薄荷，并且知道每只猫都喜欢其中的某些品种。窗边有一排 $m$ 个花盆，按顺序从 $1$ 到 $m$ 编号，你会在每个花盆里放一株猫薄荷。然后，每只猫都会被（通过绳子上的玩具）引导着，沿着花盆从 $1$ 号走到 $m$ 号。一旦一只猫到达一个装有它喜欢的猫薄荷的花盆，它就会停在那里，即使那个花盆旁已经有其他猫了。

你知道你希望每只猫停在哪一个花盆旁边。你能否找到一种摆放植物的方式来实现这个目标？

输入格式

输入的第一行包含一个整数 $t$ $(1 \leq t \leq 10000)$，表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，其中 $n$ $(1 \leq n \leq 2 \cdot 10^{5})$ 是猫的数量，$m$ $(1 \leq m \leq 2 \cdot 10^{5})$ 是猫薄荷植物的数量（也是花盆的数量）。猫薄荷植物从 $1$ 到 $m$ 编号。

接下来的 $n$ 行每行描述一只猫。该行以两个整数 $p$ 和 $k$ 开始，其中 $p$ $(1 \leq p \leq m)$ 是猫应该停下的花盆编号，$k$ $(1 \leq k \leq m)$ 是该猫喜欢的猫薄荷植物的数量。该行的其余部分包含 $k$ 个不同的整数，即该猫喜欢的植物的编号。

所有测试用例的 $n$ 的总和最多为 $2 \cdot 10^{5}$，$m$ 的总和最多为 $2 \cdot 10^{5}$，所有 $k$ 的总和最多为 $5 \cdot 10^{5}$。

输出格式

对于每个测试用例，如果可能按照上述方式安排猫薄荷植物，则输出 yes，否则输出 no。

样例

输入

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

输出

yes
no

在第一个样例中，一种可能的植物摆放顺序是 $[2,1,5,3,4]$。这样，猫 $1$ 会在 $2$ 号花盆停下，因为这是它遇到的第一个装有它喜欢的植物品种的花盆。猫 $2$ 也会在那里停下。猫 $3$ 则会一直走到 $4$ 号花盆，如图 F.1 所示。