시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 144 36 33 32.039%

문제

세상에는 N종류의 물약이 있고 클레어는 M개의 레시피를 알고있다.

레시피는 (x1, x2, ..., xk) → r 형태로 표현할 수 있고 x1번, x2번 ..., xk번 물약을 모두 섞어서 r번 물약을 만들 수 있다는 뜻이다.

현재 클레어에게는 y1번, y2번, ..., yL번 물약만 있다. 만들 수 있는 물약들을 전부 알아내주자.

클레어가 가지고 있는 각 종류의 물약의 양은 무한대라고 가정하자.

입력

첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다.

다음 M개의 줄에는 각각의 줄마다 레시피의 정보 ki, xi1, xi2, ..., xiki, ri (1 ≤ ki < N, 1 ≤ xij ≤ N, xijri)가 주어지며 이는 (xi1, xi2, ..., xiki) → ri 형태의 레시피를 의미한다.

M+2 번째 줄에는 현재 클레어가 가지고 있는 물약 종류의 수 L (1 ≤ L < N) 이 주어진다.

M+3 번째 줄에는 y1, y2, ..., yL이 주어진다.

모든 ki의 합은 400,000을 넘지 않는다.

출력

첫 번째 줄에 클레어가 만들 수 있는 물약의 개수를 출력한다.

두 번째 줄에는 만들 수 있는 물약의 번호를 오름차순으로 출력한다.

예제 입력 1

7 5
3 1 5 7 2
3 1 3 6 7
2 3 4 5
2 4 5 3
2 5 6 4
3
1 5 6

예제 출력 1

7
1 2 3 4 5 6 7

예제 입력 2

7 5
3 1 5 7 2
3 1 3 6 7
2 3 4 5
2 4 5 3
2 5 6 4
2
3 4

예제 출력 2

3
3 4 5

출처

University > 경북대학교 > 2020 Goricon H번

  • 문제를 만든 사람: exqt