Figure Fixing
Contest: Codeforces Round 726 (Div. 2)
Difficulty rating: 2200
Tags: constructive algorithms, dfs and similar, dsu, graphs, greedy, math

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 format:
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 format:
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".

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

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

Example output:
YES
NO

Editorial:
If the parity of the sum of the initial values doesn't match the parity of the sum of the target values then there is no solution. Because $$$k$$$ is an integer and we always add the value $$$2 \cdot k$$$ to the sum of the initial values in each operation it's easy to notice that the parity of the sum of the initial values never changes.
Otherwise, let's consider $$$2$$$ cases:
2) The graph is bipartite.
3) The graph is not bipartite.
If the graph is bipartite, let the nodes be coloured red and blue with the condition that all the neighbors of any red node are blue and all the neighbours of any blue node are red. Let us call $$$sum1 = \sum target_i-value_i$$$ for each blue node and $$$sum2 = \sum target_i-value_i$$$ for each red node. We want to determine if we can make $$$target_i = value_i$$$ for each node, which is equivalent to saying $$$sum1 = 0$$$ and $$$sum2 = 0$$$. We notice that the difference between $$$sum1$$$ and $$$sum2$$$ is invariant in a bipartite graph because all operations will add to $$$sum1$$$ and $$$sum2$$$ at the same time. So to make $$$sum1 = 0$$$ and $$$sum2 = 0$$$ we need $$$sum1-sum2$$$ to be equal to $$$0$$$ initially.
If the graph is not bipartite, then it is always possible because if the graph is not bipartite, it contains two neighboring vertices of the same color, which can be used to add or subtract from their color sum.