One day, a turtle gives you a tree with $n$ nodes rooted at node $x$. Each node has an initial nonnegative value; the $i$-th node has starting value $a_i$.

You want to make the values of all nodes equal to $0$. To do so, you will perform a series of operations on the tree, where each operation will be performed on a certain node. Define an operation on node $u$ as choosing a single node in $u$'s subtree$^{\text{∗}}$ and incrementing or decrementing its value by $1$. The order in which operations are performed on nodes is as follows:

• For $1 \le i \le n$, the $i$-th operation will be performed on node $i$.
• For $i > n$, the $i$-th operation will be performed on the same node as operation $i - n$.

More formally, the $i$-th operation will be performed on the $(((i - 1) \bmod n) + 1)$-th node.$^{\text{†}}$

Note that you cannot skip over operations; that is, you cannot perform the $i$-th operation without first performing operations $1, 2, \ldots, i - 1$.

Find the minimum number of operations you must perform before you can make the values of all nodes equal to $0$, assuming you pick operations optimally. If it's impossible to make the values of all nodes equal to $0$ after finite operations, output $-1$.

Input

The first line contains a single integer $t$ ($1\le t\le 100$) — the number of test cases.

The first line of each test case contains two integers $n$ and $x$ ($1 \le n \le 2000$, $1 \le x \le n$) — the number of nodes and the root of the tree.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the starting value of each node.

Each of the next $n - 1$ lines of each test case contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) representing an undirected edge from $u$ to $v$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

Output

For each test case, output a single integer denoting the minimum amount of operations needed to make all nodes $0$. If it's impossible to make all nodes $0$, output $-1$.

见题面 Input 部分

见题面 Output 部分

In the first test case, you can make the following valid sequence of operations:

• For operation $1$, decrease the value of node $1$. This is valid because $(((1 - 1) \bmod n) + 1) = 1$, and node $1$ is in the subtree of node $1$.
• For operation $2$, decrease the value of node $2$. This is valid because $(((2 - 1) \bmod n) + 1) = 2$, and node $2$ is in the subtree of node $2$.
• For operation $3$, decrease the value of node $2$. This is valid because $(((3 - 1) \bmod n) + 1) = 1$, and node $2$ is in the subtree of node $1$.