#P16579. [Euc2024]Dating

[Euc2024]Dating

题目描述

你正在开发一款完全不考虑性别的约会应用。应用中有 nn 名用户,编号为 11nn。每名用户的资料中列出了自己喜欢参加的活动。

一共有 mm 种可能的活动,编号为 11mm

若两名用户满足以下全部条件,则称他们构成一组良好匹配

  1. 两人至少有一种共同喜欢的活动;
  2. 第一名用户至少喜欢一种第二名用户不喜欢的活动;
  3. 第二名用户至少喜欢一种第一名用户不喜欢的活动。

请找出一组良好匹配;若不存在,则报告不存在。

输入格式

第一行包含两个整数 n,mn,m2n2000002\le n\le 2000001m1061\le m\le 10^6),分别表示用户数量和活动种类数。

接下来 nn 行,第 ii 行首先包含一个整数 kik_i0kim0\le k_i\le m),随后包含 kik_i 个互不相同的整数,表示用户 ii 喜欢的活动编号。

保证

k1+k2++kn106.k_1+k_2+\cdots+k_n\le 10^6.

输出格式

若存在良好匹配,第一行输出 YES,第二行输出两个整数,表示构成良好匹配的两名用户编号。

若不存在,输出 NO

若存在多组答案,输出任意一组。

样例 1

输入

3 5
3 1 2 4
5 1 2 3 4 5
2 1 5

输出

YES
3 1

说明

用户 11 和用户 33 都喜欢活动 11;用户 33 喜欢用户 11 不喜欢的活动 55,而用户 11 喜欢用户 33 不喜欢的活动 44,因此二者构成良好匹配。

用户 11 与用户 22、用户 22 与用户 33 都不构成良好匹配,因为用户 11 和用户 33 喜欢的活动集合都被用户 22 的集合包含。

样例 2

输入

3 3
1 1
1 2
3 2 3 1

输出

NO