← 返回题目列表

Codeforces · 1949/F

F. 约会

中文机器翻译题面 查看原题

您是一款完全忽略性别的约会应用程序的开发者。该应用程序有 $$$n$$$ 用户,索引从 $$$1$$$ 到 $$$n$$$。每个用户的个人资料都包含他们喜欢做的活动的列表。有 $$$m$$$ 可能的活动,索引从 $$$1$$$ 到 $$$m$$$。

如果两个用户共享至少一项活动,并且同时他们都喜欢至少一项另一用户不喜欢的活动,那么他们之间的匹配就很好。

查找一个好的匹配项(如果存在)。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 200\,000$$$, $$$1 \leq m \leq 10^6$$$) — 用户数量和活动数量。

以下 $$$n$$$ 行中的每一行都包含一个数字 $$$k_i$$$ ($$$0 \leq k_i \leq m$$$) — 用户 $$$i$$$ 喜欢的活动数量 — 后跟从 $$$1$$$ 到 $$$m$$$ 的 $$$k_i$$$ 不同整数 — 用户 $$$i$$$ 喜欢的活动。

保证$$$k_1+k_2+\cdots+k_n$$$不超过$$$10^6$$$。

输出

如果存在良好的匹配,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{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

注意

在第一个示例中,用户 $$$1$$$ 和 $$$3$$$ 形成匹配,因为他们共享活动 $$$1$$$,此外,用户 $$$3$$$ 喜欢活动 $$$5$$$(用户 $$$1$$$ 不喜欢),而用户 $$$1$$$ 喜欢活动 $$$4$$$(用户 $$$3$$$ 不喜欢)喜欢)。请注意,用户 $$$1$$$ 和 $$$2$$$ 以及用户 $$$2$$$ 和 $$$3$$$ 不形成匹配,因为不存在用户 $$$1$$$ 或 $$$3$$$ 喜欢的活动,并且用户 $$$2$$$ 不喜欢的活动。