您有一个由 $$$n$$$ 节点和 $$$m$$$ 边组成的连通无向图。第 $$$i$$$ 个节点具有值 $$$v_i$$$ 和目标值 $$$t_i$$$。
在运算中,您可以选择一条边 $$$(i, j)$$$ 并将 $$$k$$$ 添加到 $$$v_i$$$ 和 $$$v_j$$$,其中 $$$k$$$ 可以是任何整数。特别是,$$$k$$$ 可以为负数。
您的任务是确定是否有可能通过执行一些有限数量的操作(可能为零),您可以为每个节点 $$$i$$$ 实现 $$$v_i = t_i$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$),测试用例的数量。然后是测试用例。
每个测试用例的第一行包含两个整数 $$$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})$$$) — 分别是节点和边的数量。
第二行包含 $$$n$$$ 整数 $$$v_1\ldots, v_n$$$ ($$$-10^9 \leq v_i \leq 10^9$$$) — 节点的初始值。
第三行包含 $$$n$$$ 整数 $$$t_1\ldots, t_n$$$ ($$$-10^9 \leq t_i \leq 10^9$$$) — 节点的目标值。
接下来的 $$$m$$$ 行包含两个整数 $$$i$$$ 和 $$$j$$$ ,表示节点 $$$i$$$ 和节点 $$$j$$$ 之间的边 ($$$1 \leq i, j \leq n$$$, $$$i\ne j$$$)。
保证图是连通的,且同一对节点之间至多有一条边。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果每个节点在一定次数的操作后都有可能达到其目标,则打印“YES”。否则,打印“NO”。
示例
输入 #1
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
输出 #1
YES NO
注意
这是第一个测试用例的可视化(橙色值表示初始值,蓝色值表示所需值):
获取每个节点所需值的一种可能的操作顺序如下:
- 操作$$$1$$$:将$$$2$$$添加到节点$$$2$$$和$$$3$$$。
- 操作$$$2$$$:将$$$-2$$$添加到节点$$$1$$$和$$$4$$$。
- 操作$$$3$$$:将$$$6$$$添加到节点$$$3$$$和$$$4$$$。
现在我们可以看到,我们总共向节点 $$$1$$$ 添加了 $$$-2$$$,向节点 $$$2$$$ 添加了 $$$2$$$,向节点 $$$3$$$ 添加了 $$$8$$$,向节点 $$$4$$$ 添加了 $$$4$$$,这使得每个节点都准确地达到了其所需的值。
对于第二个测试用例的图表,不可能获得目标值。