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

[NOI Online 2022 提高组] 讨论

Background

After consideration by the administrators, we plan to store the community testdata separately in the last Subtask. The score of these test points is 0, but failing any of these test points will be considered as not passing this problem.

In this problem, there is an issue where the test point numbers in judge records appear disordered. This is caused by a naming conflict in the community testdata. However, we guarantee that their relative order is not messed up.

Community testdata provider: @AutumnKite, strengthened by @tiger2005.

Problem Description

There are nn people taking a mock contest, and the mock contest has nn problems.
Two people will discuss only when there are problems that both of them can solve, and neither person’s set of solvable problems contains the other’s.
(Define the set of problems that person ii can solve as SiS_i. That is, when $S_x\cap S_y\neq\varnothing\land S_x\not\subseteq S_y\land S_y\not\subseteq S_x$, person xx and person yy will discuss.)
To make the mock contest more effective, please find a pair of people who will discuss, or determine that none exist.

Input Format

The first line contains a positive integer TT, the number of test cases. For each test case:
The first line contains a positive integer nn, the number of people and the number of problems.
Then follow nn lines. In the ii-th line, the first natural number kik_i indicates that the ii-th person can solve kik_i problems. Then there are kik_i positive integers; each integer xx means that the ii-th person can solve problem xx.

Output Format

For each test case:
If there is no pair of people who will discuss, output NO.
Otherwise, output YES on the first line, and output two positive integers xx and yy on the second line, indicating that person xx and person yy will discuss.
If there are multiple solutions, output any one.

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

Hint

[Sample 2]

See discuss/discuss2.in and discuss/discuss2.ans in the attachment.

[Constraints and Hints]

For all test points: let m=kim=\sum k_i in a test case. Then 1T51\le T\le 5, 1n1061\le \sum n\le {10}^6, 1m2×1061\le \sum m\le 2\times {10}^6, and 0kin0\le k_i\le n.

The specific limits for each test point are shown in the table below:

Translated by ChatGPT 5