클레어와 물약
시간 제한1초메모리 제한256 MB
여러 포션을 조합해 다른 포션을 만드는 레시피들과 처음 가진 포션 목록이 주어질 때, 만들 수 있는 모든 포션을 구한다.
문제
세상에는 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, ri ≤ N, xij ≠ ri)가 주어지며, 이는 (xi1, xi2, ..., xiki) → ri 형태의 레시피를 의미한다.
M+2번째 줄에는 현재 클레어가 가지고 있는 물약 종류의 수 L (1 ≤ L < N)이 주어진다.
M+3번째 줄에는 y1, y2, ..., yL (1 ≤ yi ≤ N)이 주어진다.
모든 ki의 합은 400,000을 넘지 않는다.
출력
첫 번째 줄에 클레어가 만들 수 있는 물약의 개수를 출력한다.
두 번째 줄에는 만들 수 있는 물약의 번호를 오름차순으로 출력한다.