시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB59161437.838%

문제

내 친구 용감한 쿠키가 고민에 빠졌다고 한다. 용감한 쿠키는 요즘 쿠키런 킹덤이라는 게임을 하는데, 해당 게임에서는 n가지 종류의 자원 중 일부를 이용하여 건물을 짓게 된다. 자원은 이미 지어진 건물을 통하여 만들 수 있다. 또한, 건물을 짓는 데에는 1초가 걸리고, 자원을 만드는 데에는 0초가 걸린다고 한다. 그리고 각 건물로부터 필요한 자원과 생산 가능한 자원의 최대 가짓수는 n과 30중 낮은 값(= min(n, 30)) 이라고 한다. 

건물의 종류 n개, 이미 지어진 건물의 수 m개, 자원의 종류 n개, 제한 시간을 t, 맨 처음 시간(이미 지어진 건물 포함)은 0초라고 할 때, 용감한 쿠키는 현재 지어진 건물로 정해진 시간 이내에 최종적으로 건설할 수 있는 건물이 무엇이 있는지 궁금하다며 빨리 알고 싶다고 한다. 하지만 용감한 쿠키는 머리가 나빠 구할 수가 없다고 한다. 

내 친구가 너의 친구이고 너의 친구가 내 친구이지 않은가? 얼른 친구 용감한 쿠키를 도와주자.

입력

입력은 첫번째 줄에 건물의 개수 n과 이미 지어진 건물의 개수 m, 제한 시간 t가 주어진다. (1 ≤ n ≤ 100,000, 1 ≤ m ≤ n, 0 ≤ t ≤ n)

두번째 줄에는 서로 다른 m개의 번호가 주어지며, 이는 이미 지어진 건물의 번호이다.

이후 n개의 줄에 각 건물마다 생산 가능한 자원의 가짓수와 그 자원 번호가 공백으로 나뉘어서 주어진다.

그 이후 n - m개의 줄에는 아직 지어지지 않은 건물의 번호와 건물마다 필요로 하는 자원의 가짓수, 그 자원 번호가 공백으로 나뉘어서 주어진다.

이 때, 각 건물에서 생산되는 자원과 건물을 지을 때 필요한 자원의 가짓수는 1 이상이다. 건물, 자원의 종류는 n가지이며, 이는 번호로 구분되어 주어진다. (1 ≤ 자원 및 건물 번호 ≤ n)

각 건물로부터 필요한 자원과 생산 가능한 자원의 최대 가짓수는 n과 30을 넘지 않는다. 즉, 최대 가짓수는 n과 30중에 낮은 값보다 작거나 같다. (최대 가짓수 ≤ min(n, 30))

출력

첫번째 줄에는 결과적으로 지을 수 있는 건물의 개수를 출력하고, 두번째 줄에는 지을 수 있는 건물의 번호를 오름차순으로 모두 출력하시오.

예제 입력 1

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

예제 출력 1

3
1 2 3

힌트

이미 생산된 건물로부터 만들 수 있는 자원은 무한정적으로 생산 가능하다.

출처

University > 경북대학교 > 2021 Goricon F번