첩보 확산

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

요약

방향성 연락 그래프와 적 스파이 집합이 주어질 때, 모든 아군 스파이가 메시지를 받고 적 스파이는 받지 않도록 직접 메시지를 보내야 하는 최소 횟수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, DFS, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

당신은 선량 요원 보호 센터(BAPC) 소속 스파이이고, 최근 일급 기밀 문서를 손에 넣었다. 이 소식을 조직의 동료 스파이 전원에게 알리려고 한다. 한 명씩 직접 비밀 메시지를 보낼 수도 있지만 시간이 너무 오래 걸린다. 다행히 다른 스파이도 각자 연락망이 있어서 메시지를 대신 퍼뜨려 준다.

문제는 연락망에 적 조직의 스파이가 섞여 있다는 점이다. 이들은 메시지를 받으면 곧바로 적 조직에 넘긴다. 그래서 적 스파이에게는 메시지가 절대 닿으면 안 된다. 다행히 누가 배신자인지 당신은 알고 있으므로 그들을 피할 수 있다.

메시지를 보내는 방법은 두 가지다. 비밀 메시지를 받은 스파이는 내용이 기밀임을 알고 다른 누구에게도 말하지 않는다. 공개 메시지를 받은 스파이는 자신이 연락할 수 있는 모든 스파이에게 그 내용을 알린다. 그 스파이 역시 기밀로 여기지 않으므로 자신이 연락할 수 있는 모든 스파이에게 다시 알리고, 이 전달은 계속 이어진다. 전에 같은 메시지를 받은 적이 있는 스파이도 다시 받으면 똑같이 퍼뜨린다. 누가 적 스파이인지 드러나면 안 되므로, 특정 연락처만 빼고 알리라고 지시할 수는 없다.

적 스파이가 한 명이라도 메시지를 받으면 실패다. 반대로 적이 아닌 스파이는 모두 메시지를 받아야 한다. 두 조건을 지키면서 당신이 직접 메시지를 보내는 스파이 수를 최소로 하려고 한다. 몇 명에게 보내야 하는가?

입력

첫 줄에 세 정수 $S$ , $E$ , $C$ 가 주어진다. $S$ ( $1 \le S \le 50000$ )는 연락망에 있는 스파이의 수이며 당신은 포함하지 않는다. $E$ ( $0 \le E \le S$ )는 적 스파이의 수, $C$ ( $0 \le C \le 100000$ )는 스파이 사이 연결의 수이다.

다음 $C$ 개 줄에는 두 정수 $S_1$ , $S_2$ ( $0 \le S_1 < S$ , $0 \le S_2 < S$ )가 주어진다. 스파이 $S_1$ 이 스파이 $S_2$ 에게 연락할 수 있다는 뜻이고, 연결은 한쪽 방향으로만 성립한다. 같은 연결이 여러 번 주어질 수 있고 $S_1 = S_2$ 일 수도 있다.

마지막 줄에는 적 스파이의 번호 $E$ 개가 공백으로 구분되어 주어진다. $E = 0$ 이면 이 줄은 비어 있거나 아예 없을 수 있다.

당신은 연락망의 모든 스파이에게 직접 메시지를 보낼 수 있다.

출력

다른 스파이에게 보내야 하는 메시지 수의 최솟값을 한 줄에 출력한다. 비밀 메시지와 공개 메시지를 모두 센다.

예제3

예제 1
입력
```
4 1 3
0 1
1 2
2 3
1
```
예상 출력
```
2
```
예제 2
입력
```
4 0 4
0 2
0 1
2 1
2 3
```
예상 출력
```
1
```
예제 3
입력
```
4 2 5
0 1
0 2
0 3
1 3
2 3
1 2
```
예상 출력
```
2
```