CF1949F.Dating
提高+/省选-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
你是一个约会软件的开发者。该软件有 $ n $ 个用户,编号为 $ 1\sim n $ 。每个用户的都有一个他们喜欢做的活动列表。每个人最多有 $ m $ 个喜欢的活动,编号为 $ 1\sim m $ 。
如果两个用户都喜欢的活动个数 $ \ge1 $ ,并且这两个用户中都各有至少一个自己喜欢而对方不喜欢的活动,那么这两个用户之间就称为是好的匹配。
如果存在好的匹配,请查找匹配项。
输入格式
第一行包含 $ 2 $ 个整数 $ n,m $ (2≤n≤2×105,1≤m≤106),分别表示用户数量和活动数量。
之后 $ n $ 行,每行开头包含一个正整数 $ k_i $ (0≤ki≤m),表示编号为 $ i $ 的用户喜欢的活动数量。之后给出在 $ 1 \sim m $范围内的 $ k_i $ 个正整数,表示用户 $ i $ 喜欢的活动编号。
保证$ k_1+k_2+···+k_n \le 10^6 $。
输出格式
如果存在好的匹配,输出 $ \texttt{YES} $ ,否则输出 $ \texttt{NO} $ 。
如果存在好的匹配,则第二行输出 $ 2 $ 个整数,表示能够匹配的两个用户的编号。
样例解释
样例1中,由于用户 $ 1 $ 和 $ 3 $ 都喜欢活动 $ 1 $ ,且用户3喜欢活动 $ 5 $ 而用户 $ 1 $ 不喜欢,用户 $ 1 $ 喜欢活动 $ 4 $ 而用户 $ 3 $ 不喜欢,所以他们之间存在好的匹配。
同时,用户 $ 1 $ 和 $ 2 $ 、用户 $ 2 $ 和 $ 3 $ 之间都不存在好的匹配,因为不存在用户 $ 1 $ , $ 3 $ 喜欢而用户 $ 2 $ 不喜欢的活动。
Translate Provided by @qsy8515 .
输入输出样例
输入#1
3 5 3 1 2 4 5 1 2 3 4 5 2 1 5
输出#1
YES 3 1
输入#2
3 3 1 1 1 2 3 2 3 1
输出#2
NO
输入解题思路,AI测评打分。不知道怎么写?