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


-----Examples-----

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.

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Greedy algorithms

Mathematics

Spanning trees


Solutions:
import itertools

def is_digraph(edges):
	n = len(edges)
	color = [None] * n
	color[0] = 1
	q = [0]
	while q:
		pos = q.pop()
		c = 1 - color[pos]
		for nxt in edges[pos]:
			if color[nxt] is None:
				color[nxt] = c
				q.append(nxt)
			elif color[nxt] != c:
				return (False, None)
	return (True, color)

def solve():
	(n, m) = map(int, input().split())
	v = list(map(int, input().split()))
	t = list(map(int, input().split()))
	edges = [list() for __ in range(n)]
	parity = 0
	for __ in range(m):
		(i, j) = map(int, input().split())
		i -= 1
		j -= 1
		edges[i].append(j)
		edges[j].append(i)
	for x in itertools.chain(v, t):
		parity ^= x & 1
	if parity:
		print('NO')
		return
	(di, colors) = is_digraph(edges)
	if not di:
		print('YES')
	else:
		sums = [0, 0]
		for (i, c) in enumerate(colors):
			sums[c] += t[i] - v[i]
		(a, b) = sums
		print('YES') if a == b else print('NO')
for testcases in range(int(input())):
	solve()


def isTwoColorable(gr, n, cols):
	cols[1] = 0
	(qu, ind) = ([1], 0)
	isBip = True
	while ind < len(qu):
		node = qu[ind]
		ind += 1
		for cnode in gr[node]:
			if cols[cnode] == -1:
				cols[cnode] = cols[node] ^ 1
				qu.append(cnode)
			else:
				isBip &= cols[cnode] != cols[node]
	return isBip

def solve(gr, n, v, t):
	if sum(v) % 2 != sum(t) % 2:
		return 'NO'
	cols = [-1] * (n + 1)
	if isTwoColorable(gr, n, cols):
		gsm = [0, 0]
		for i in range(1, n + 1):
			gsm[cols[i]] += t[i - 1] - v[i - 1]
		if gsm[0] == gsm[1]:
			return 'YES'
		return 'NO'
	return 'YES'
for case in range(int(input())):
	(n, m) = list(map(int, input().split()))
	V = list(map(int, input().split()))
	T = list(map(int, input().split()))
	gr = [[] for i in range(n + 1)]
	for ed in range(m):
		(u, v) = list(map(int, input().split()))
		gr[u].append(v)
		gr[v].append(u)
	ans = solve(gr, n, V, T)
	print(ans)


for test in range(int(input())):
	(n, m) = map(int, input().split())
	lv = [int(i) for i in input().split()]
	t = [int(i) for i in input().split()]
	lv.insert(0, 0)
	t.insert(0, 0)
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(U, V) = map(int, input().split())
		g[U].append(V)
		g[V].append(U)
	color = [-1] * (n + 1)
	two_set = 1
	L = int(0)
	R = int(0)
	color[1] = 0
	q = [0, 1]
	while q:
		u = q.pop()
		if color[u]:
			L += lv[u] - t[u]
		else:
			R += lv[u] - t[u]
		for v in g[u]:
			if color[v] == -1:
				color[v] = color[u] ^ 1
				q.append(v)
			elif color[u] == color[v]:
				two_set = 0
	res = 1
	if two_set:
		res &= L == R
	else:
		res &= L + R & 1 == 0
	if res:
		print('YES')
	else:
		print('NO')


def chbi(adj, c):
	c[0] = 1
	q = [0]
	while q:
		i = q.pop()
		for j in range(len(adj[i])):
			n = adj[i][j]
			if c[n] == -1:
				c[n] = 1 - c[i]
				q.append(n)
			elif c[n] == c[i]:
				return False
	return True
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	v = list(map(int, input().split()))
	t = list(map(int, input().split()))
	c = [-1] * n
	adj = [[] for i in range(n)]
	for i in range(m):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	if (sum(v) - sum(t)) % 2 != 0:
		print('NO')
	elif chbi(adj, c):
		s1 = s2 = 0
		for i in range(n):
			if c[i] == 0:
				s1 += t[i] - v[i]
			else:
				s2 += t[i] - v[i]
		if s1 != s2:
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	v = list(map(int, input().split()))
	t = list(map(int, input().split()))
	d = [t[i] - v[i] for i in range(n)]
	edge = []
	x = [-1] * n
	for _ in range(n):
		edge.append([])
	for _ in range(m):
		(a, b) = map(int, input().split())
		edge[a - 1].append(b - 1)
		edge[b - 1].append(a - 1)
	if sum(d) % 2 != 0:
		print('NO')
	else:
		isbgph = 0
		x[0] = 0
		p = [0]
		while len(p) > 0:
			i = p.pop()
			for nxt in edge[i]:
				if x[nxt] == -1:
					x[nxt] = 1 - x[i]
					p.append(nxt)
				elif x[nxt] == x[i]:
					isbgph = 1
		if isbgph == 1:
			print('YES')
		else:
			sum1 = sum([d[i] for i in range(n) if x[i] == 0])
			sum2 = sum([d[i] for i in range(n) if x[i] == 1])
			if sum1 == sum2:
				print('YES')
			else:
				print('NO')