407967: GYM102953 4 School Contact Tracing

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

4. School Contact Tracingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You go to a school with $$$n$$$ students, all of which can be identified by a unique student ID from 1 to $$$n$$$, inclusive. The school has $$$m$$$ classes, each consisting of $$$k$$$ students.

Unfortunately, $$$c$$$ students just tested positive for COVID-19, and the school is figuring out which other students need to go into quarantine due to the $$$c$$$ students testing positive.

Since the school is being very cautious, they decide to have any students in at least one class with the $$$c$$$ students quarantine, but the school decides to extend the rule and have any students in a class with a quarantined student quarantine as well. This continues in a "chain reaction" process, until there are no more additional students that have to quarantine.

Given the $$$c$$$ students that just tested positive, figure out the ID's of any additional students that have to quarantine (not including the original $$$c$$$ students).

Input

The first line of input consists of three space-separated integers $$$n$$$ $$$(1 <= n <= 10^5)$$$, $$$m$$$ $$$(1 <= m <= 10^5)$$$, and $$$k$$$ $$$(1 <= k <= 10^5)$$$, $$$m * k <= 10^5$$$: the number of students in the school, the number of classes in the school, and the number of students in each class, respectively.

The next $$$m$$$ lines each contain $$$k$$$ distinct space-separated integers: the student ID's of each student in each class.

The next line contains a single positive integer $$$c$$$ $$$(1 <= c <= n)$$$: the number of students that recently tested positive for COVID-19.

The next line contains $$$c$$$ distinct space-separated positive integers: the student ID's of the students that recently tested positive.

Output

Output a single positive integer $$$q$$$: the number of additional students that have to quarantine.

Then, output a single line consisting of $$$q$$$ space-separated integers in ascending order: the number of students that will have to quarantine (not including the students that already tested positive).

Scoring

Subtask 1 (14 points): $$$(1 <= n, m, k, m*k <= 1000)$$$

Subtask 2 (9 points): no additional constraints

ExamplesInput
13 4 5
1 3 5 6 7
3 5 8 6 1
2 9 11 10 4
4 11 9 13 2
3
1 5 8
Output
3
3 6 7 
Input
13 4 5
1 3 5 6 7
3 5 8 6 1
2 9 10 11 4
4 11 9 13 2
4
1 5 8 4
Output
8
2 3 6 7 9 10 11 13 
Input
30 10 5
18 5 2 20 15
7 18 16 9 17
23 26 15 24 21
8 29 10 23 7
29 17 10 2 21
2 14 20 7 11
21 20 4 15 23
10 18 6 16 9
20 12 11 8 2
18 6 20 16 19
1
29
Output
21
2 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 23 24 26 

加入题单

上一题 下一题 算法标签: