P4308.第1题-多多的工作配对

1000ms

Difficulty: 3

所属公司 : 拼多多

算法与标签>模拟

题目内容

现有 $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$ " (均不包含双引号).

输入

输出

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$ .

输入

预期输出（选填）