F. Figure Fixing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a connected undirected graph made of $$$n$$$ nodes and $$$m$$$ edges. The $$$i$$$-th node has a value $$$v_i$$$ and a target value $$$t_i$$$.

In an operation, you can choose an edge $$$(i, j)$$$ and add $$$k$$$ to both $$$v_i$$$ and $$$v_j$$$, where $$$k$$$ can be any integer. In particular, $$$k$$$ can be negative.

Your task to determine if it is possible that by doing some finite number of operations (possibly zero), you can achieve for every node $$$i$$$, $$$v_i = t_i$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$), the number of test cases. Then the test cases follow.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$, $$$n-1\leq m\leq \min(2\cdot 10^5, \frac{n(n-1)}{2})$$$) — the number of nodes and edges respectively.

The second line contains $$$n$$$ integers $$$v_1\ldots, v_n$$$ ($$$-10^9 \leq v_i \leq 10^9$$$) — initial values of nodes.

The third line contains $$$n$$$ integers $$$t_1\ldots, t_n$$$ ($$$-10^9 \leq t_i \leq 10^9$$$) — target values of nodes.

Each of the next $$$m$$$ lines contains two integers $$$i$$$ and $$$j$$$ representing an edge between node $$$i$$$ and node $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i\ne j$$$).

It is guaranteed that the graph is connected and there is at most one edge between the same pair of nodes.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$ and the sum of $$$m$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, if it is possible for every node to reach its target after some number of operations, print "YES". Otherwise, print "NO".

Example
Input
2
4 4
5 1 2 -3
3 3 10 1
1 2
1 4
3 2
3 4
4 4
5 8 6 6
-3 1 15 4
1 2
1 4
3 2
3 4
Output
YES
NO
Note

Here is a visualization of the first test case (the orange values denote the initial values and the blue ones the desired values):

One possible order of operations to obtain the desired values for each node is the following:

  • Operation $$$1$$$: Add $$$2$$$ to nodes $$$2$$$ and $$$3$$$.
  • Operation $$$2$$$: Add $$$-2$$$ to nodes $$$1$$$ and $$$4$$$.
  • Operation $$$3$$$: Add $$$6$$$ to nodes $$$3$$$ and $$$4$$$.

Now we can see that in total we added $$$-2$$$ to node $$$1$$$, $$$2$$$ to node $$$2$$$, $$$8$$$ to node $$$3$$$ and $$$4$$$ to node $$$4$$$ which brings each node exactly to it's desired value.

For the graph from the second test case it's impossible to get the target values.