410461: GYM104023 F Mooncake Delivery

Melon is a rabbit living on the moon who is responsible for delivering moon cakes at the Mid-Autumn Festival every year. Besides the Earth, many other planets also have a demand for mooncakes. Therefore, Melon needs to consume her fairy power to travel among different planets when delivering mooncakes.

There are $$$n$$$ planets numbered from $$$1$$$ to $$$n$$$, along with $$$m$$$ tunnels. Each tunnel undirectedly connects two planets. Each planet $$$i$$$ has a color $$$c_i$$$ and a cost $$$w_i$$$ indicating the power that Melon needs to consume to land on it.

In order to save the power for interstellar travel, Melon will use a special skill: planting cinnamon trees. Initially, no cinnamon trees are planted on any of the planets. Once Melon lands on a planet without a cinnamon tree, she will immediately plant a cinnamon tree there, but she will not plant more than one cinnamon tree on each planet. If a planet is already planted with a cinnamon tree, Melon will not consume any power when she lands on that planet again. In addition, when she is on planet $$$i$$$, she can select a planet $$$j$$$ that is planted with a cinnamon tree and is not colored $$$c_i$$$, and then remotely cut down the cinnamon tree on planet $$$j$$$ and recover $$$w_j$$$ power.

Formally, Melon can perform any one of the following actions at any time on planet $$$u$$$:

• Move to an adjacent planet $$$v$$$ that is not planted with a cinnamon tree via a tunnel, consume $$$w_v$$$ power, and plant a cinnamon tree on planet $$$v$$$.
• Move to an adjacent planet that is planted with a cinnamon tree via a tunnel, without consuming power and without planting additional trees.
• Select a planet $$$v$$$ that is planted with a cinnamon tree and is not colored $$$c_u$$$, and then remotely cut down the cinnamon tree on planet $$$v$$$ (i.e., no cinnamon tree is planted on planet $$$v$$$ thereafter) and recover $$$w_v$$$ power. Please note that this action can be performed multiple times on the same planet.

Melon's fairy power cannot be lower than $$$0$$$, so she must prepare enough power before she departs. Melon wants to know the minimum amount of power she needs to prepare for the travel from the starting planet $$$s$$$ to the terminal planet $$$t$$$. Specially, Melon needs to consume $$$w_s$$$ power and plant a cinnamon tree on the starting planet $$$s$$$.

The first line contains an integer $$$T$$$ ($$$1 \le T \le 100$$$), indicating the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 300$$$, $$$1 \le m \le \dfrac{n(n-1)}{2}$$$), indicating the number of planets and tunnels.

The second line of each test case contains $$$n$$$ integers $$$c_1,c_2,\dots,c_n$$$ ($$$1 \le c_i \le n$$$), indicating the color of each planet.

The third line of each test case contains $$$n$$$ integers $$$w_1,w_2,\dots,w_n$$$ ($$$1 \le w_i \le 10^9$$$), indicating the power to be consumed on each planet.

Each of the following $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$), indicating an undirected tunnel between planet $$$u$$$ and $$$v$$$. It is guaranteed that there is at most one tunnel between any two different planets, and there exists a path between any two different planets.

It is guaranteed that $$$\sum n \le 300$$$ over all test cases.

Output $$$n$$$ lines, each of which contains $$$n$$$ integers separated by spaces. The integer in the $$$i$$$-th row and $$$j$$$-th column indicates the minimum amount of power that needs to be prepared for the travel from the starting planet $$$i$$$ to the terminal planet $$$j$$$. Specially, output $$$0$$$ when $$$i=j$$$.

1
4 4
1 1 2 3
1 2 4 5
1 2
2 3
3 4
1 4

0 3 7 6
3 0 6 8
6 6 0 8
6 6 7 0

For the sample, here is a way to go from planet $$$3$$$ to planet $$$1$$$ with $$$6$$$ initial power:

1. Consume $$$4$$$ power and plant a cinnamon tree on planet $$$3$$$. (Remaining power: $$$2$$$)
2. Move to planet $$$2$$$, consume $$$2$$$ power and plant a cinnamon tree on it. (Remaining power: $$$0$$$)
3. Cut down the cinnamon tree on planet $$$3$$$ and recover $$$4$$$ power. (Remaining power: $$$4$$$)
4. Move to planet $$$1$$$, consume $$$1$$$ power and plant a cinnamon tree on it. (Remaining power: $$$3$$$)