#P8252. [NOI Online 2022 提高组] 讨论

    ID: 7544 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>2022Special JudgeO2优化NOI Online

[NOI Online 2022 提高组] 讨论

题目背景

经过管理员的考虑,我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分,但是没有通过其中的任何测试点将会视为此题不通过。

这一题中出现了评测记录测试点编号错乱的问题,是民间数据命名方式冲突导致的。但是我们保证其相对顺序没有混乱。

民间数据提供者:@AutumnKite,由 @tiger2005 进行加强。

题目描述

nn 个人正在打模拟赛,模拟赛有 nn 道题目。
有两人都会的题目并且没有人会的题目包含另一个人时,两者之间才会讨论。
(定义第 ii 个人会的题目的集合为 SiS_i ,即当 $S_x\cap S_y\neq\varnothing\land S_x\not\subseteq S_y\land S_y\not\subseteq S_x$ 时,第 xx 人和第 yy 人会讨论)
为了让模拟赛的效果更好,希望你可以找出一对会讨论的人或判断不存在。

输入格式

第一行一个正整数 TT 表示数据组数,对于每组数据:
第一行一个正整数 nn 表示人数和题目数量。
接下来 nn 行,第 ii 行第一个自然数 kik_i 表示第 ii 个人会 kik_i 道题。接下来 kik_i 个正整数,每个数 xx 表示第 ii 个人会第 xx 道题。

输出格式

对于每组数据:
如果没有会讨论的人,输出 NO
否则第一行输出 YES,第二行输出两个正整数 xxyy,表示第 xx 人和第 yy 人会讨论。
如果有多种方案,输出任意一种即可。

2
5
4 1 2 3 5
3 1 2 3
2 1 2
1 1
1 4
4
3 1 2 3
3 2 3 4
0
4 1 2 3 4
NO
YES
1 2

提示

【样例 2】

见附件中的 discuss/discuss2.indiscuss/discuss2.ans

【数据范围与提示】

对于所有测试点:令一组数据中 m=kim=\sum k_i,则 1T51\le T\le 51n1061\le \sum n\le {10}^61m2×1061\le \sum m\le 2\times {10}^60kin0\le k_i\le n

每个测试点的具体限制见下表: