P5402: 讨论(discuss)

传统题
1.000s 时间限制
512MB 内存限制
3 提交
3 解决

【题目描述】
【题目描述】
n 个人正在打模拟赛,模拟赛有 n 道题目。
有两人都会的题目并且没有人会的题目包含另一个人时,两者之间才会讨论。
(定义第 i 个人会的题目的集合为 Si ,即当 Sx ∩ Sy  ≠ ∅∧ Sx ⊈ Sy ∧ Sy ⊈ Sx 时,第 x 人和第 y 人会讨论)
为了让模拟赛的效果更好,希望你可以找出一对会讨论的人或判断不存在。
【输入】

【输入格式】

从文件 discuss.in 中读入数据。

第一行一个正整数 T 表示数据组数,对于每组数据:

第一行一个正整数 n 表示人数和题目数量。

接下来 n 行,第 i 行第一个自然数 ki 表示第 i 个人会 ki 道题。接下来 ki 个正整数,每个数 x 表示第 i 个人会第 x 道题。

【输出】

【输出格式】

输出到文件 discuss.out 中。

对于每组数据:

如果没有会讨论的人,输出 NO

否则第一行输出 YES,第二行输出两个正整数 x y,表示第 x 人和第 y 人会讨论。

如果有多种方案,输出任意一种即可。


【样例输入】复制
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.in discuss/discuss2.ans

【数据范围与提示】

对于所有测试点:令一组数据中 m = ∑ki,则 1 ≤ T ≤ 51 ≤ ∑n ≤ 1061 ≤ ∑m ≤ 2 × 106 0 ≤ ki ≤ n

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

测试点编号

特殊限制

1

n ≤ 300

2 ∼ 3

n ≤ 1000

4

n ≤ 5000

5 ∼ 7

n ≤ 5 × 104

8

ki ≤ 10

9 ∼ 10


 

题目类型~

NOIOnline2022提高级 

咻咻~

提交答案 状态