题目描述

给定一棵 $n$ 个点的树，树上第 $i$ 个点带非负整数点权 $a_i$。

定义树上一条简单路径的价值是简单路径上所有点的点权构成集合的 $\text{mex}$，即最小的没有在集合中出现过的非负整数。

求树上所有简单路径的价值的最大值，以及价值为这个最大值的简单路径数量，其中我们认为 $x$ 到 $y$ 和 $y$ 到 $x$ 是两条路径。

由于一些特殊的原因，树上的点权分布比较特殊。具体而言，对于任意某个特定点权 $v$，所有的点权为 $v$ 的点构成的点集合：

都存在树上的一条简单路径，使得 $S(v)$ 中的所有点都在这条简单路径上。

输入格式

本题单个测试点内包含多组测试数据。

第一行一个整数 $T$（$1\le T\le 10$），表示数据组数。

对于每组数据，第一行一个整数 $n$（$3\le n \le 7\times10^4$），表示树的点数。

第二行 $n$ 个整数 $a_1,a_2,...,a_n$（$0\le a_i \le n$），表示树上每个点的点权。

接下来 $n-1$ 行，每行两个整数 $x,y$（$1\le x,y \le n$），表示树上有一条连接点 $x,y$ 的边，保证构成一棵树。

测试点保证所有数据 $\sum n \le 3.6\times10^5$。

输出格式

对于每组数据输出一行两个整数，分别表示价值的最大值和对应的简单路径数量。

输入样例

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

输出样例

5 2
3 6
3 6