At your networking event, there are $$$n$$$ deals waiting to happen.

Each deal needs exactly two people, and every person is waiting for exactly one deal. So there are $$$2n$$$ people in total, and each deal ID $$$1 \ldots n$$$ appears on exactly two people's badges.

For corporate reasons, the organisers place each person on a unique vertex in a tree with $$$2n$$$ vertices. Vertex $$$v$$$ hosts a person with badge $$$a_v$$$.

Deal $$$i$$$ is sealed if, when the event begins, the two people with badge $$$i$$$ are on adjacent vertices. Each sealed deal contributes $$$w_i$$$ to your earnings.

Before the event starts, you are allowed one reshuffle:

Choose any (potentially empty) set of edges such that no two chosen edges share a vertex (i.e., the edges form a matching).
For every chosen edge $$$(u, v)$$$, swap the people at vertices $$$u$$$ and $$$v$$$.

After reshuffling, what is the maximum you can earn from this event?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The next line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \leq w_i \leq 10^5$$$), where $$$w_i$$$ denotes the profit from deal $$$i$$$.

The next line contains $$$2n$$$ integers $$$a_1, a_2, \ldots, a_{2n}$$$. It is guaranteed that each value $$$1, 2, \ldots, n$$$ appears exactly twice in $$$a$$$.

The next $$$2n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v, \leq 2n, u \neq v$$$) — denoting that an edge connects nodes $$$u$$$ and $$$v$$$.

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

Output

For each test case, output a single integer — the maximum total earning after a reshuffle.

Note

Test 1. Swap edges $$$(1,2)$$$ and $$$(3,4)$$$ (they don't share vertices). Then the two 1s become adjacent on edge $$$(2,3)$$$, earning $$$w_1=10$$$, which beats keeping the existing 2—2 adjacency worth 3.

Test 2. The tree is a star. Swapping $$$(1,2)$$$ moves badge 1 to the center, making it adjacent to the other 1, earning $$$w_1=8$$$.

Test 3. Swap $$$(1,2), (3,4), (5,6)$$$ to seal two deals at once: edge $$$(2,3)$$$ becomes 1—1 (gain 4) and edge $$$(4,5)$$$ becomes 3—3 (gain 7), total 11.

Closer

Examples