QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100

#10341. Dating

统计

你是某款完全忽略性别的约会应用的开发者。该应用共有 $n$ 名用户,编号从 1 到 $n$。每位用户的个人资料中都包含他们喜欢的活动列表。共有 $m$ 种可能的活动,编号从 1 到 $m$。

如果两名用户至少有一个共同喜欢的活动,且同时两人都至少有一个对方不喜欢的活动,那么这两名用户之间的匹配就是“好的”。

如果存在好的匹配,请找出它。

输入格式

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

接下来的 $n$ 行,每行包含一个整数 $k_i$ ($0 \le k_i \le m$),表示用户 $i$ 喜欢的活动数量,随后是 $k_i$ 个 1 到 $m$ 之间的不同整数,表示用户 $i$ 喜欢的活动。

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

输出格式

如果存在好的匹配,输出 YES。否则,输出 NO。

如果存在好的匹配,在下一行输出两个整数,即构成匹配的两名用户的编号。

样例

输入 1

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

输出 1

YES
3 1

说明 1

用户 1 和用户 3 构成了一个匹配,因为他们共同喜欢活动 1,此外,用户 3 喜欢活动 5(用户 1 不喜欢),而用户 1 喜欢活动 4(用户 3 不喜欢)。注意,用户 1 和用户 2,以及用户 2 和用户 3 并不构成匹配,因为不存在用户 1 或用户 3 喜欢而用户 2 不喜欢的活动。

输入 2

3 3
1 1
1 2
3 2 3 1

输出 2

NO

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.