ITAI 바이러스

면접 대비

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

요약

바이러스가 발견된 도시와 도로 하나로 직접 연결된 도시를 모두 세합니다.

난이도: 쉬움10점 중 2점
유형: 그래프, 구현
정답자: 아직 제출이 없습니다

문제

Insane Transferable Abnormal Illness, 줄여서 ITAI는 어느 도시의 남쪽 지역에서 처음 발견된 바이러스성 질병이다. 이 바이러스에 걸린 사람은 "이타이, 이타이!"라고 쉬지 않고 소리를 지른다.

바이러스는 어떤 도시에 나타나면 둘로 분열해서 그 도시에 닿아 있는 모든 도로를 따라 퍼진다. 처음 있던 도시에도 바이러스는 그대로 남는다. 다만 ITAI 바이러스는 약해서, 다른 도시로 옮겨 간 뒤에는 더 퍼지지 못하는 약한 바이러스로 변한다.

한 나라에 도시가 $N$ 개 있고, 번호는 1번부터 $N$ 번까지다. 도로는 $M$ 개다. 보건부가 조사해서 $K$ 개 도시에서 바이러스를 찾아냈다. 이 $K$ 개 도시의 바이러스는 모두 아직 퍼질 수 있는 새 바이러스다.

바이러스가 모두 퍼지고 난 뒤에 바이러스가 있는 도시가 몇 개인지 구하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. ( $1 \le T \le 10$ )

각 테스트 케이스는 다음과 같이 주어진다.

첫째 줄에 도시의 수 $N$ , 도로의 수 $M$ , 바이러스가 발견된 도시의 수 $K$ 가 주어진다. ( $1 \le N \le 1000$ , $1 \le M \le 2N$ , $0 \le K \le N$ )
다음 $M$ 개 줄에는 도로를 나타내는 두 정수 $A$ 와 $B$ 가 주어진다. ( $1 \le A \le N$ , $1 \le B \le N$ ) 이 도로는 도시 $A$ 와 도시 $B$ 를 양방향으로 잇는다. 같은 도시 쌍을 잇는 도로가 여러 개일 수 있고, $A$ 와 $B$ 가 같을 수도 있다.
다음 줄에는 바이러스가 발견된 도시의 번호 $K$ 개가 주어진다. $K$ 가 0이면 이 줄은 비어 있다.

출력

각 테스트 케이스마다 바이러스가 있는 도시의 수를 한 줄에 하나씩 출력한다.

힌트

바이러스가 있는 도시는 처음에 바이러스가 발견된 도시와, 그 도시와 도로로 직접 이어진 도시를 모두 합한 것이다. 도로를 두 번 이상 건너가야 닿는 도시에는 바이러스가 퍼지지 않는다.

예제2

예제 1

입력

예상 출력

2
4
4

예제 2

입력

10
4 4 3
2 2
4 3
1 2
2 3
3 4 2
1 1 1
1 1
1
1 1 0
1 1

7 2 0
5 3
7 5

2 1 0
2 1

4 6 0
4 3
1 3
4 4
2 2
2 3
1 3

9 12 8
2 6
6 2
2 1
8 2
8 5
3 3
2 3
9 6
9 1
1 2
8 3
4 6
9 6 2 1 4 3 7 5
1 2 1
1 1
1 1
1
3 3 2
2 3
1 2
3 2
3 2
12 1 9
4 5
9 2 1 7 10 11 3 8 6

예상 출력