물통 시스템

동일한 물통 $\mathbf{N}$개로 이루어진 물통 시스템이 있다. 이 시스템은 각 물통이 정점인 트리로 나타낼 수 있다. 물통들은 $\mathbf{N}-1$개의 양방향 파이프로 서로 연결되어 있다. 서로 연결된 두 물통은 항상 인접한 층에 놓여 있다. 형식적으로, 두 물통 $a$와 $b$가 서로 연결되어 있다면 $|level_a - level_b | = 1$이다. 물통 $1$는 가장 아래층에 놓여 있다. 각 물통은 바로 아래층의 물통 정확히 하나와 연결되어 있지만, 바로 위층의 물통과는 연결되어 있지 않거나 그 이상과 연결될 수 있다. 유일한 예외는 물통 $1$로, 아래쪽에 연결된 물통이 없다. 각 물통의 최대 용량은 $1$리터이며, 처음에는 모든 물통이 비어 있다. 파이프의 용량은 $0$리터라고 가정한다. 다시 말해 파이프는 물을 저장하지 않고, 어느 방향으로든 물이 통과할 수 있게만 한다.

물통 시스템의 예인 다음 그림을 살펴보자.

시스템의 첫 번째 층은 물통 $1$(루트) 하나로 구성된다. 물통 $1$는 바로 위층인 $2$층에 있는 물통 $2$ 및 물통 $3$와 연결되어 있다. 물통 $2$는 $3$층에 있는 물통 $4$와도 연결되어 있다.

$\mathbf{Q}$개의 쿼리가 주어진다. 각 쿼리에는 물통을 나타내는 정수 $i$가 하나 포함된다. 각 쿼리마다 물통 $i$에 물 $1$리터를 추가한다.

다음 그림은 여러 조건에서 시스템 내 물의 흐름을 보여 준다.

$1$단계에서는 물통 $3$에 물 $1$리터를 추가한 후, 아래층의 물통들이 아직 비어 있으므로 물이 아래로 흐른다. $2$단계에서는 물통 $3$에 물 $1$리터를 추가한 후 물이 아래로 흐르지만, 물통 $1$가 이미 완전히 차 있으므로 물이 물통 $2$와 $3$에 균등하게 분배된다. $3$단계에서는 물통 $3$에 물 $1$리터를 추가한 후 물통 $2$와 $3$가 완전히 찬다. $4$단계에서는 물통 $3$에 물 $1$리터를 추가한 후 물이 물통 $4$까지 위로 밀려 올라가며, 그 물통도 완전히 찬다.

위 예제에서 보인 것처럼 같은 층의 물통에는 같은 양의 물이 담긴다. 모든 쿼리를 처리한 후 완전히 찬 물통의 개수를 구한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{Q} \le \mathbf{N}$. 주어진 물통 시스템은 트리임이 보장된다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 65535$. 물통 시스템은 완전 이진 트리이다.

테스트 세트 2

시간 제한: 60초. $1 \le \mathbf{N} \le 10^4$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 $\mathbf{N}$과 $\mathbf{Q}$이 주어진다. 여기서 $\mathbf{N}$는 물통의 개수이고, $\mathbf{Q}$은 쿼리의 개수이다. 다음 $\mathbf{N}-1$개의 줄에는 두 정수 $i$와 $j$가 주어진다. ($1 \le i, j \le \mathbf{N}$, 그리고 $i ≠ j$) 이는 $i$번째 물통과 $j$번째 물통이 연결되어 있다는 의미이다. 다음 $\mathbf{Q}$개의 각 줄에는 물 $1$리터를 추가해야 하는 물통을 나타내는 정수 $i$ 하나가 주어진다. ($1 \le i \le \mathbf{N}$)

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$은 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 쿼리를 처리한 후 완전히 찬 물통의 개수이다.

예제 케이스 #1에는 물통이 $\mathbf{N} = 1$개 있다. 물통 $1$에 물 $1$리터를 추가한 후 완전히 찬 물통의 개수는 $1$개이다.

예제 케이스 #2에는 물통이 $\mathbf{N} = 3$개 있다. 모든 쿼리를 처리한 후 완전히 찬 물통의 개수는 $1$개이다.

물통 $1$에 물 $1$리터를 추가한 후: 물통 $1$는 완전히 차고, 나머지 물통은 비어 있다. 물통 $2$에 물 $1$리터를 추가한 후: 물통 $1$는 완전히 차고, 물통 $2$와 $3$는 일부만 차 있다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에는 물통이 $\mathbf{N} = 4$개 있다. 모든 쿼리를 처리한 후 완전히 찬 물통의 개수는 $4$개이며, 이는 문제 설명에서 이미 설명했다.

예제 케이스 #2에는 물통이 $\mathbf{N} = 5$개 있다. 모든 쿼리를 처리한 후 완전히 찬 물통의 개수는 $1$개이다.

물통 $4$에 물 $1$리터를 추가한 후: 물통 $1$는 완전히 차고, 나머지 물통은 비어 있다. 물통 $5$에 물 $1$리터를 추가한 후: 물통 $1$는 완전히 차고, 물통 $2$와 $3$는 일부만 차 있으며, 나머지 물통은 비어 있다.