F. Tree Operationstime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis 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$$$.InputThe 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$$$.OutputFor 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$$$.ExampleInput52 11 21 23 22 1 32 13 24 11 1 0 11 22 31 412 614 4 5 6 12 9 5 11 6 2 1 123 910 66 124 33 15 119 75 61 82 85 11 10Output3
6
5
145
0
NoteIn 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$$$.