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

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

Tree Operations

Examples