CF1949F Dating

题目描述

你是一个约会软件的开发者。该软件有 $ n $ 个用户,编号为 $ 1\sim n $ 。每个用户的都有一个他们喜欢做的活动列表。每个人最多有 $ m $ 个喜欢的活动,编号为 $ 1\sim m $ 。 如果两个用户都喜欢的活动个数 $ \ge1 $ ,并且这两个用户中都各有至少一个自己喜欢而对方不喜欢的活动,那么这两个用户之间就称为是好的匹配。 如果存在好的匹配,请查找匹配项。

输入格式

第一行包含 $ 2 $ 个整数 $ n,m $ ($2\le n \le 2\times 10^5,1\le m\le 10^6$),分别表示用户数量和活动数量。 之后 $ n $ 行,每行开头包含一个正整数 $ k_i $ ($0\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 $ ,且用户$3$喜欢活动 $ 5 $ 而用户 $ 1 $ 不喜欢,用户 $ 1 $ 喜欢活动 $ 4 $ 而用户 $ 3 $ 不喜欢,所以他们之间存在好的匹配。 同时,用户 $ 1 $ 和 $ 2 $ 、用户 $ 2 $ 和 $ 3 $ 之间都不存在好的匹配,因为不存在用户 $ 1 $ , $ 3 $ 喜欢而用户 $ 2 $ 不喜欢的活动。 Translate Provided by @qsy8515 .

说明/提示

In the first sample, users $ 1 $ and $ 3 $ form a match, because they share activity $ 1 $ , and, furthermore, user $ 3 $ likes activity $ 5 $ (which user $ 1 $ does not like) and user $ 1 $ likes activity $ 4 $ (which user $ 3 $ does not like). Note that users $ 1 $ and $ 2 $ , as well as users $ 2 $ and $ 3 $ , do not form a match, as there is no activity that users $ 1 $ or $ 3 $ like, and user $ 2 $ doesn't like.