33905번 - 영일 마을에 살고 있는 엄은 친구의 집에 가고 싶다

문제

영일 마을에는 엄과 $N$명의 친구들이 살고 있다. 영일 마을은 $N+1$개의 집이 $M$개의 도로로 연결되어 있으며, 엄의 집은 1ドル$번, 친구들의 집은 각각 2ドル$번부터 $N+1$번까지의 번호가 매겨져 있다. 엄의 집에서 모든 친구들의 집에 방문하는 경로가 있음이 보장된다.

모처럼 여유로운 엄은 자신의 집에서 출발하여 모든 친구들의 집을 방문하려 했지만, $K$명의 친구들이 집 문을 잠그고 여행을 떠나버렸다. 이때, 문이 잠긴 집과 연결된 도로는 모두 사용할 수 없다.

$K$명의 친구들이 집 문을 잠그고 여행을 떠났을 때, 엄이 방문할 수 있는 친구 집의 수를 구하여라.

입력

첫 번째 줄에 친구의 수 $N,ドル 도로의 수 $M,ドル 여행을 떠난 친구의 수 $K$가 주어진다. $(1 \le N \le 5 ,円 000;$ $N \le M \le \min(\displaystyle \frac{N(N+1)}{2},10,000円);$ 1ドル \le K \le N)$

두 번째 줄부터 $M$개의 줄에 도로의 정보 $u,v$가 공백으로 구분되어 주어진다. 이는 $u$번 집과 $v$번 집이 양방향 도로로 연결되어 있다는 것을 의미한다. 같은 도로의 정보는 주어지지 않는다. $(1 \le u,v \le N+1; u \neq v)$

마지막 줄에 여행을 떠난 $K$명의 친구들의 집 번호가 중복 없이 공백으로 구분되어 주어진다. 엄의 집 번호는 주어지지 않는다.

입력으로 주어지는 모든 수는 정수이다.

출력

엄이 방문할 수 있는 친구 집의 수를 출력한다.

제한

힌트