#CF1949F. 匹配交友
匹配交友
F. 匹配交友
单个测试点时间限制: 秒 单个测试点内存限制: 兆字节
你是一款交友软件的开发者,该软件不考虑性别差异。软件中有 个用户,编号从 到 。每个用户的个人资料中列出了自己喜欢的活动。总共有 种可能的活动,编号从 到 。
如果两个用户之间满足以下条件,则称他们为良好匹配:
- 他们至少共同喜欢一项活动;
- 同时,双方都至少有一项对方不喜欢的活动。
如果存在良好匹配,请找出一对;否则说明不存在。
输入格式
第一行包含两个整数 和 (,)——用户数和活动数。
接下来 行,每行首先给出一个整数 (),表示用户 喜欢的活动数量,随后跟着 个互不相同的整数,表示该用户喜欢的活动编号。
保证所有 之和不超过 。
输出格式
如果存在良好匹配,输出 YES,并在下一行输出任意一对符合条件的用户编号。
否则输出 NO。
样例输入 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
样例说明
第一个样例中,用户 和 是良好匹配:
- 共同喜欢活动 ;
- 用户 喜欢活动 ,而用户 不喜欢;
- 用户 喜欢活动 ,而用户 不喜欢。
用户 与 、 与 都不是良好匹配,因为用户 喜欢所有对方喜欢的活动,对方没有 不喜欢的活动。