감시 고양이

언덕과 숲으로 둘러싸인 작은 마을 코쿠르코프에 쥐 문제가 생겼다. 이 마을은 아늑한 펍과 친절한 사람들로 알려져 오랫동안 평화로웠다. 그런데 쥐들이 나타났다. 이 쥐들은 똑똑하고 빠르며, 동시에 여러 곳에 있는 것처럼 보인다. 마을에서 가장 인기 있는 펍들을 차지하고 천장 대들보 사이를 뛰어다니며 빵 부스러기를 갉아 먹어 큰 골칫거리가 되었다.

코쿠르코프에는 $N$개의 장소와 정확히 $N - 1$개의 도로가 있다. 도로를 따라가면 어떤 장소에서든 다른 모든 장소에 갈 수 있다. 각 도로는 두 장소를 잇는다.

시의회는 가장 큰 펍 U Nacpané Myši에서 긴급 회의를 열었다. 쥐들이 도시를 가로지르며 일정한 패턴으로 움직이는 것이 확인되었다. 각 쥐는 정확히 두 개의 굴을 가지고 있고, 그 두 굴 사이만 오간다. 각 굴은 장소 중 한 곳에 있다. 또한 쥐는 평소 다니는 경로의 대략 중간쯤에서 취약해진다는 사실도 관찰되었다. 형식적으로 쓰면, 쥐의 굴이 장소 $A$와 $B$에 있을 때, 장소 $C$가 $A$에서 $B$로 가는 경로 위에 있고 $|d(C, A)-d(C, B)| \le 1$을 만족할 때에만 쥐는 $C$에서 취약하다. 여기서 $d(X, Y)$는 $X$에서 $Y$까지 경로 위의 도로 개수다. 쥐가 취약한 장소는 여러 곳일 수 있고, 자기 굴에서도 취약할 수 있다.

마을은 도시 곳곳에 감시 고양이를 배치하기로 했다. 감시 고양이는 쥐가 취약한 장소에 앉아 있으면 그 쥐를 쫓아낼 수 있다. 고양이 한 마리가 쫓아낼 수 있는 쥐의 수에는 제한이 없다. 감시 고양이는 게을러서 정해진 장소에 앉아 있을 뿐 자리를 옮기지 않는다.

감시 고양이는 비싸기 때문에 시의회는 구입할 고양이 수를 최소로 하려 한다. 이 일을 도와달라.

첫 줄에 두 정수 $N$과 $K$가 주어진다($2 \le N \le 10^5$, $0 \le K \le 10^5$). 각각 장소의 수와 쥐의 수다.

이어지는 $N - 1$개의 줄에는 두 정수 $U$와 $V$($0 \le U, V \le N - 1$)가 주어진다. 장소 $U$와 $V$가 도로로 직접 연결되어 있다는 뜻이다.

이어지는 $K$개의 줄에는 두 정수 $P$와 $Q$($0 \le P, Q \le N - 1$)가 주어진다. 쥐 한 마리의 굴이 장소 $P$와 $Q$에 있다는 뜻이다. $P \ne Q$가 보장된다.

모든 쥐를 결국 쫓아낼 수 있도록 배치해야 하는 감시 고양이의 최소 마리 수를 정수 하나로 출력한다.