Lookout Towers

A kingdom has $N$ villages connected by $N-1$ two-way roads, so that it is possible to travel between any two villages using the roads. The distance between two villages is the minimum number of roads needed to travel from one village to the other.

Some villages have a watchtower, and there are at least two watchtowers in the kingdom. The king wants to know how close the two nearest watchtowers are, and how many pairs of watchtowers are that close.

Input

The first line contains an integer $N$ ($2 \leq N \leq 2 \times 10^{5}$) indicating the number of villages. Each village is identified by a distinct integer from $1$ to $N$.

The second line contains $N$ integers ${W_1}, {W_2}, \ldots, {W_N}$, where $W_i=1$ if village $i$ has a watchtower, and $W_i=0$ otherwise. At least two of these values are $1$.

Each of the next $N-1$ lines contains two integers $U$ and $V$ ($1 \leq U,V \leq N$ and $U \neq V$), indicating that there is a two-way road between villages $U$ and $V$. It is guaranteed that it is possible to travel between any two villages using the roads.

Output

Output a single line with two integers: the minimum distance between two different watchtowers, followed by the number of unordered pairs of watchtowers at that distance.

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

2 2

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

2 4