P5886 Hello, 2020!

At the moment when the hour hand and the minute hand overlap at “zero”, the ticking sound announces the arrival of a new year. In the past year, the world has been unpredictable. You in front of the screen may have only heard of “OI” not long ago, or you may have temporarily ended your contest journey; you may have dominated the contest and topped the leaderboard, or you may have borne the loneliness of failure by yourself. No matter what, the past is still the past, and the future is still the future. Let this problem be the beginning, and welcome your 2020!

In this contest, there are $n$ problem setters and $m$ contestants. The problem setters are numbered from $1$ to $n$, and the contestants are numbered from $1$ to $m$. After the contest ends, the final ranking of contestants is a permutation of $1$ to $m$, and all ranks are distinct. After registration ends, the $i$-th problem setter looked at the registration list and said to the other problem setters: “I think only these $k_i$ contestants might finally rank first. They are $a_{i,1},a_{i,2},\dots,a_{i,k_i}$. No one else can possibly end up in first place.” The problem setter of the problem on your screen learned in advance, through a time tunnel, who the contestant that finally ranks first is. The problem setter told you all $n$ predictions made by these problem setters, and also told you that exactly $p$ problem setters’ predictions are correct. Please determine which contestants could possibly end up in first place, and output their IDs in increasing order.

Read the input from standard input. The first line contains three positive integers $n,m,p$, representing the number of problem setters, the number of contestants, and the number of correct predictions. The next $n$ lines each start with a non-negative integer $k_i$, indicating how many contestants the $i$-th problem setter predicts could finally rank first; then follow $k_i$ positive integers $a_{i,1},a_{i,2},\dots,a_{i,k_i}$, indicating the contestant IDs that this problem setter predicts could finally rank first.

Write the output to standard output. The first line outputs a non-negative integer, indicating the number of contestants who could possibly end up in first place. The second line outputs these contestants’ IDs in increasing order.

Subtask 1 ($6\%$): $n\leq 20$, $m\leq 20$. Subtask 2 ($30\%$): $n\leq 100$, $m\leq 100$, $\sum k_i \leq 10^4$. Subtask 3 ($24\%$): $n\leq 1000$, $m\leq 1000$. Subtask 4 ($40\%$): no special constraints. Constraints for all data: $1\leq n\leq 10^5$, $1\leq m\leq 10^6$, $0\leq \sum k_i \leq 10^6$, $0\leq p\leq n$. Translated by ChatGPT 5