题目描述

Lucas 在一座拥有 $N$ 个电力节点的城市中担任工程师。这些节点构成一个网络，可以看作是一个具有 $N$ 个顶点和 $N-1$ 条边的连通图。城市正面临停电，所有节点都没有电力供应，Lucas 负责处理这一情况。

每个节点都有一个固定的电容量。$A_i$ 是第 $i$ 个节点的电容量。由于资源限制，Lucas 只能为其中一个节点供电，但其他节点可以根据其连接和电容量接收电力。如果第 $i$ 个节点接收到电力，那么它会将电力传输到所有与它直接相连且电容量严格小于 $A_i$ 的节点。当没有符合条件的节点时，传输停止。请帮助 Lucas 确定最多有多少个节点可以接收到电力。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含一个整数 $N$，表示城市中节点的数量。

第二行包含 $N$ 个整数。其中第 $i$ 个整数是 $A_i$，表示第 $i$ 个节点的电容量。

接下来的 $N-1$ 行，每行包含两个整数 $X_i$ 和 $Y_i$，表示节点 $X_i$ 和 $Y_i$ 直接相连。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是能够接收到电力的最大节点数。

样例

2
5
1 2 3 4 3
1 3
2 3
4 3
4 5
6
1 2 3 3 1 4
3 1
3 2
3 4
4 5
1 6

Case #1: 5
Case #2: 3

说明/提示

在样例 #1 中，最优方案是为第 $4$ 个节点供电。电力最终会传输到所有节点。

如果为第 $3$ 个节点供电，它会将电力传输到第 $1$ 个和第 $2$ 个节点，但不会传输到第 $4$ 个节点。在这种情况下，最终只有三个节点能接收到电力。

在样例 #2 中，最优方案是为第 $3$ 个节点供电。它会将电力传输到第 $1$ 个和第 $2$ 个节点。注意，电力不会传输到第 $4$ 个节点，因为它的电容量不小于第 $3$ 个节点的电容量。

如果为第 $6$ 个节点供电，它只会传输到第 $1$ 个节点。

如果为第 $4$ 个节点供电，它只会传输到第 $5$ 个节点。

限制条件

对于 $30\%$ 的数据

• $1 \le T \le 15$
• $1 \le N \le 10^3$

对于 $100\%$ 的数据：

• $1 \le T \le 100$
• $1 \le N \le 2 \times 10^5$
• 对于所有 $i$，$1 \le A_i \le 10^9$
• 对于所有 $i$，$1 \le X_i, Y_i \le N$
• 所有节点属于同一个连通网络