F. Tree Operations
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
This really says a lot about our society.

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$$$.

$$$^{\text{∗}}$$$The subtree of a node $$$u$$$ is the set of nodes for which $$$u$$$ lies on the shortest path from this node to the root, including $$$u$$$ itself.

$$$^{\text{†}}$$$Here, $$$a \bmod b$$$ denotes the remainder from dividing $$$a$$$ by $$$b$$$.

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$$$.

Example
Input
5
2 1
1 2
1 2
3 2
2 1 3
2 1
3 2
4 1
1 1 0 1
1 2
2 3
1 4
12 6
14 4 5 6 12 9 5 11 6 2 1 12
3 9
10 6
6 12
4 3
3 1
5 11
9 7
5 6
1 8
2 8
5 1
1 1
0
Output
3
6
5
145
0
Note

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$$$.