Formica Sokobanica

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

요약

나무 모양 둥지에서 견과가 든 방에 들어갈 때 인접한 빈 방으로 견과를 밀어내는 규칙 아래, 개미가 들어갈 수 있는 방의 개수를 구합니다.

난이도: 보통10점 중 7점
유형: 트리, DFS, 그리디
정답자: 아직 제출이 없습니다

문제

새로 발견된 개미 종 Formica sokobanica는 독특한 습성 때문에 곤충학자들의 관심을 끌었다. 이 개미들은 집단을 이루지 않는다. 개체마다 자기만의 둥지를 만들고, 먹이인 견과를 둥지 안에 보관한다.

둥지는 통로로 연결된 작은 방 여러 개로 이루어진다. 방은 견과보다 조금 클 뿐이어서 공기가 흐를 만큼의 여유만 남는다. 개미는 견과가 들어 있는 방에 들어갈 수 없다. 통로는 견과 크기에 딱 맞으므로, 공기가 통하도록 견과를 통로에 남겨 두어서는 안 된다.

견과가 들어 있는 방에 들어가려면, 개미는 그 견과를 방과 통로로 연결된 인접한 빈 방 중 하나로 밀어내야 한다. 개미가 온 방을 제외하고 인접한 빈 방이 없으면 견과를 밀어낼 수 없고, 개미는 그 방에 들어갈 수 없다.

곤충학자 중 한 명인 Dr. Myrmink가 전형적인 둥지의 도면을 그렸다. 도면에는 어느 방에 견과가 있는지, 개미가 처음 어느 방에 있는지가 표시되어 있다. 개미가 도달해서 들어갈 수 있는 방의 개수를 구하라.

견과를 한 빈 방으로 밀어내면 일부 방에 도달할 수 없게 되고, 다른 방으로 밀어내면 그 방들에 계속 도달할 수 있을 수 있다. 선택의 조합은 여러 가지일 수 있다. 이때 적어도 하나의 선택 조합으로 도달할 수 있는 방을 모두 센다. 개미가 처음 있는 방에는 견과가 없고, 둥지에는 사이클이 없다고 가정해도 된다.

입력

첫 줄에 방의 개수 $n$ 과 견과의 개수 $m$ 이 주어진다. $1 \le n \le 2 \times 10^5$ , $0 \le m < n$ 이다. 방은 1번부터 $n$ 번까지 번호가 매겨져 있고, 개미는 처음에 1번 방에 있다.

다음 $n-1$ 개 줄에는 통로가 연결하는 두 방의 번호 $x_i$ , $y_i$ 가 주어진다. $1 \le x_i \le n$ , $1 \le y_i \le n$ , $x_i \ne y_i$ 이며, 같은 두 방을 잇는 통로는 하나뿐이다.

나머지 $m$ 개 줄에는 견과가 들어 있는 방의 번호 $a_k$ ( $2 \le a_k \le n$ )가 한 줄에 하나씩 주어진다. $a_k$ 는 모두 서로 다르다.

n m
x1 y1
.
.
.
xn-1 yn-1
a1
.
.
.
am

출력

개미가 도달해서 들어갈 수 있는 방의 개수를 한 줄에 출력한다.

예제4

예제 1
입력
```
7 2
1 2
2 3
3 4
4 5
5 6
5 7
2
4
```
예상 출력
```
2
```
예제 2
입력
```
8 2
1 2
2 3
3 4
2 5
5 6
6 7
2 8
2
6
```
예상 출력
```
7
```
예제 3
입력
```
7 3
1 2
2 3
3 4
3 5
4 6
5 7
2
4
5
```
예상 출력
```
2
```

예제 4

입력

예상 출력