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.