전기

Ben은 전기 접속점이 $\mathbf{N}$개 있는 도시에서 엔지니어로 일한다. 이 접속점들은 네트워크를 이루며, 정점이 $\mathbf{N}$개이고 간선이 $\mathbf{N}-1$개인 연결 그래프로 나타낼 수 있다. 도시에 정전이 발생하여 어떤 접속점도 전기를 공급받지 못하고 있으며, Ben이 이 상황을 처리할 책임을 맡고 있다.

각 접속점에는 고정된 전기 용량이 있다. $\mathbf{A_i}$는 $i$번째 접속점의 전기 용량이다. 자원의 제약으로 인해 Ben은 단 하나의 접속점에만 전기를 공급할 수 있지만, 다른 접속점들은 연결 상태와 용량에 따라 전기를 공급받을 수 있다. $i$번째 접속점이 전기를 공급받으면, $i$번째 접속점과 직접 연결되어 있고 용량이 $\mathbf{A_i}$보다 엄격히 작은 모든 접속점에도 전기가 전달된다. 조건을 만족하는 접속점이 없으면 전달이 멈춘다. Ben을 도와 전기를 공급받을 수 있는 접속점 수의 최댓값을 구한다.

제한

시간 제한: 40초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{A_i} \le 10^9$. 모든 $i$에 대해 $1 \le \mathbf{X_i}, \mathbf{Y_i} \le \mathbf{N}$. 모든 접속점은 하나의 연결된 네트워크에 속한다.

테스트 세트 1

$1 \le \mathbf{N} \le 10^3$.

테스트 세트 2

최대 15개의 케이스에 대해: $1 \le \mathbf{N} \le 2 \times 10^5$. 나머지 케이스에 대해: $1 \le \mathbf{N} \le 10^3$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 도시의 접속점 수를 나타내는 정수 $\mathbf{N}$이 주어진다. 다음 줄에는 $\mathbf{N}$개의 정수가 주어진다. $i$번째 정수는 $i$번째 접속점의 전기 용량인 $\mathbf{A_i}$이다. 다음 $\mathbf{N}-1$개의 줄에는 각각 두 정수 $\mathbf{X_i}$와 $\mathbf{Y_i}$가 주어지며, 이는 접속점 $\mathbf{X_i}$와 $\mathbf{Y_i}$가 서로 직접 연결되어 있음을 의미한다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 (1부터 시작), $y$는 전기를 공급받을 수 있는 접속점 수의 최댓값이다.

예제 케이스 #1에서 최적의 방법은 넷째 접속점에 전기를 공급하는 것이다. 그러면 결국 모든 접속점에 전기가 전달된다. 셋째 접속점에 전기를 공급하면 첫째 접속점과 둘째 접속점에는 전기가 전달되지만, 넷째 접속점에는 전달되지 않는다. 이 경우 최종적으로 접속점 세 개만 전기를 공급받을 수 있다.

예제 케이스 #2에서 최적의 방법은 셋째 접속점에 전기를 공급하는 것이다. 그러면 첫째 접속점과 둘째 접속점에 전기가 전달된다. 넷째 접속점의 용량은 셋째 접속점의 용량보다 엄격히 작지 않으므로 넷째 접속점에는 전기가 전달되지 않는다는 점에 유의한다. 여섯째 접속점에 전기를 공급하면 첫째 접속점에만 전달된다. 넷째 접속점에 전기를 공급하면 다섯째 접속점에만 전달된다.