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≤1062\le n \le 2\times 10^5,1\le m\le 10^6),分别表示用户数量和活动数量。

之后 $ n $ 行,每行开头包含一个正整数 $ k_i $ (0≤ki≤m0\le k_i \le 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 $ ,且用户33喜欢活动 $ 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测评打分。不知道怎么写?

首页