화학 반응

면접 대비

시간 제한1초메모리 제한512 MB

요약

보유한 화합물에서 시작해 기질이 모두 갖춰진 반응을 반복 적용해 새로 만들 수 있는 화합물 수를 구합니다.

난이도: 보통10점 중 5점
유형: BFS, 그래프, 큐
정답자: 아직 제출이 없습니다

문제

바이텍은 최근 화학에 푹 빠져 자기만의 실험실을 만들었다. 이미 여러 화합물과 다양한 반응을 실행할 수 있는 도구를 갖추었고, 이제 가진 것을 활용해 아직 가지고 있지 않은 화합물을 몇 종류나 만들 수 있는지 궁금해한다.

바이텍이 이미 가진 화합물은 모두 무한히 있다고 가정한다. 어떤 반응은 그 반응에 필요한 모든 반응물(substrate)을 바이텍이 가지고 있을 때 실행할 수 있으며, 실행하면 그 반응의 모든 생성물(product)을 얻는다. 이렇게 얻은 생성물은 다시 다른 반응의 재료로 쓸 수 있다.

바이텍이 가진 화합물과 실행할 수 있는 반응을 읽어, 아직 가지고 있지 않지만 만들어 낼 수 있는 화합물의 개수를 구하는 프로그램을 작성하라.

입력

첫째 줄에 세 정수 $n$ , $k$ , $r$ ( $1 \le n \le 10^6$ , $1 \le k \le n$ , $1 \le r \le 10^5$ )가 공백 하나로 구분되어 주어진다. 각각 바이텍이 아는 화합물의 수, 바이텍이 가진 화합물의 수, 실행할 수 있는 반응의 수를 뜻한다.

둘째 줄에는 바이텍이 가진 화합물의 번호를 나타내는 서로 다른 $k$ 개의 정수 $a_i$ ( $1 \le a_i \le n$ )가 공백으로 구분되어 주어진다.

이어지는 $r$ 개의 줄에는 각각 반응 하나가 설명된다. 먼저 반응물의 개수를 나타내는 정수 $s_j$ ( $1 \le s_j \le 10$ )가 오고, 그 뒤에 $s_j$ 개의 반응물 번호가 온다. 이어서 생성물의 개수를 나타내는 정수 $p_j$ ( $1 \le p_j \le 10$ )가 오고, 그 뒤에 $p_j$ 개의 생성물 번호가 온다. 모든 화합물 번호는 $1$ 이상 $n$ 이하이다. 한 반응의 반응물 번호는 서로 다르고 생성물 번호도 서로 다르지만, 같은 화합물이 한 반응의 반응물이면서 동시에 생성물일 수도 있다(이 경우 촉매 역할을 한다). 한 반응을 설명하는 모든 수는 공백 하나로 구분된다.

출력

바이텍이 아직 가지고 있지 않지만, 가진 화합물로부터 적절한 반응을 실행하여 만들 수 있는 화합물의 개수를 정수 하나로 출력한다.

힌트

예시에서 네 반응은 다음과 같다.

$1 + 2 \to 3 + 4$
$4 + 1 \to 3$
$2 + 3 \to 2 + 1 + 5$
$5 + 6 \to 1 + 8 + 2$

바이텍은 처음에 화합물 $1$ 과 $2$ 를 가지고 있다. 첫 번째 반응으로 $3$ 과 $4$ 를 얻고, 이어서 세 번째 반응으로 $5$ 를 만들 수 있다. 반면 화합물 $6$ , $7$ , $8$ 은 만들 수 없다. 따라서 새로 만들 수 있는 화합물은 $3$ 개( $3$ , $4$ , $5$ )이다.

예제3

예제 1

입력

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

예상 출력

예제 2
입력
```
3 1 1
1
1 1 2 2 3
```
예상 출력
```
2
```

예제 3

입력

예상 출력