解题思路

• 按题意从 f₁ 到 fₙ 依次处理：对每个前端的偏好列表，从高到低找第一个尚未被占用的后端并占用之；若整份清单都被占了，则无法全匹配。

• 这就是对题目给定贪心过程的直接模拟，无需额外的稳定性或最大匹配算法。

• 实现要点：

  • 用大小为 n+1 的布尔数组 used 标记后端是否已被占用。
  • 对第 i 个前端的 k 个候选后端按序检查，遇到未占用则标记并继续处理下一个前端；若都占用则直接判定本组数据为 NO（但仍需把输入读完）。
  • 因为总输入规模满足 ∑k < 1e6，顺序扫描即可。

题目内容

现有 $n$ 个前端工程师 $f_1,f_2,f_3,...,f_n$ 和 $n$ 个后端工程师 $b_1,b_2,..., b_n$ .

每个前端工程师都有一份想要合作的后端工程师清单,清单按照想要合作的优先级从高到低给出,并且每位后端工程师只能与一位前端工程师合作.

多多在构思合作方案,打算依次处理 ,,九,..,,前端的合作清单,并且对于每个清单按优先级从高到低寻找可合作的后端,如果找到的后端还没有合作对象,那么他们将达成合作关系.请问如果按照上述方案,使得每位前端工程师都能成功匹配到后端工程师的话,输出"YES”,否则输出"NO"(均不包含双引号)

输入描述

第一行,包含一个正整数 $T(1 ≤T≤ 10)$ 代表测试数据的组数

对于每组测试数据,分别有 $n+1$ 行

第一行,仅有一个正整数 $n(1 ≤n≤ 10^4)$

接下来 $n$ 行,每行先给出一个正整数 $k(1 ≤k≤ n)$ 代表此前端工程师的合作清单中后端工程师的数量.

接下来给出 $k$ 个不同的正整数,分别代表按优先级从高到低给出的后端工程师的编号 $b_i(1 ≤ b_i≤ n)$

保证每组数据中 $k$ 的总和小于 $10^6$

输出描述

对于每组数据,仅输出一行.

如果按照上述方案,可以全部匹配的话,输出 "$YES$”，否则输出 "$NO$" (均不包含双引号).

样例1

输入

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

输出

YES
NO
NO

说明

对于第一组数据:

前端 $f_1$ 按顺序从左到右匹配到后端 $b_2$

前端 $f_2$ 按顺序从左到右匹配到后端 $b_1$

前端 $f_3$ 按顺序从左到右匹配到后端 $b_3$

前端 $f_4$ 按顺序从左到右匹配到后端 $b_4$

可以完全匹配,输出 $YES$ .

对于第二组数据:

前端 $f_1$ 按顺序从左到右匹配到后端 $b_1$

前端 , 没有匹配到后端,不能完全匹配,输出 $NO$ .

对于第三组数据:

前端 $f_1$ 按顺序从左到右匹配到后端 $b_2$

前端 $f_2$ 没有匹配到后端不能完全匹配,输出 $NO$ .