201061: [AtCoder]ARC106 B - Values

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

Given is a simple undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects Vertex $c_i$ and Vertex $d_i$. Initially, Vertex $i$ has the value $a_i$ written on it. You want to change the values on Vertex $1$, $\ldots$, Vertex $N$ to $b_1$, $\cdots$, $b_N$, respectively, by doing the operation below zero or more times.

  • Choose an edge, and let Vertex $x$ and Vertex $y$ be the vertices connected by that edge. Choose one of the following and do it:
    • Decrease the value $a_x$ by $1$, and increase the value $a_y$ by $1$.
    • Increase the value $a_x$ by $1$, and decrease the value $a_y$ by $1$.

Determine whether it is possible to achieve the objective by properly doing the operation.

Constraints

  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq M \leq 2 \times 10^5$
  • $-10^9 \leq a_i,b_i \leq 10^9$
  • $1 \leq c_i,d_i \leq N$
  • The given graph is simple, that is, has no self-loops and no multi-edges.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$a_1$ $\cdots$ $a_N$
$b_1$ $\cdots$ $b_N$
$c_1$ $d_1$
$\vdots$
$c_M$ $d_M$

Output

Print Yes if it is possible to achieve the objective by properly doing the operation, and No otherwise.


Sample Input 1

3 2
1 2 3
2 2 2
1 2
2 3

Sample Output 1

Yes

You can achieve the objective by, for example, doing the operation as follows:

  • In the first operation, choose the edge connecting Vertex $1$ and $2$. Then, increase $a_1$ by $1$ and decrease $a_2$ by $1$.
  • In the second operation, choose the edge connecting Vertex $2$ and $3$. Then, increase $a_2$ by $1$ and decrease $a_3$ by $1$.

This sequence of operations makes $a_1=2$, $a_2=2$, and $a_3=2$.


Sample Input 2

1 0
5
5

Sample Output 2

Yes

The objective may be achieved already in the beginning.


Sample Input 3

2 1
1 1
2 1
1 2

Sample Output 3

No

There is no way to do the operation to achieve the objective.


Sample Input 4

17 9
-905371741 -999219903 969314057 -989982132 -87720225 -175700172 -993990465 929461728 895449935 -999016241 782467448 -906404298 578539175 9684413 -619191091 -952046546 125053320
-440503430 -997661446 -912471383 -995879434 932992245 -928388880 -616761933 929461728 210953513 -994677396 648190629 -530944122 578539175 9684413 595786809 -952046546 125053320
2 10
6 12
9 11
11 5
7 6
3 15
3 1
1 9
10 4

Sample Output 4

Yes

Input

题意翻译

### 题目描述 有一个由 $N$ 顶点和 $M$ 边构成的简单无向图。第 $i$ 条边连接顶点 $c_i$ 和顶点 $d_i$。 开始时,顶点 $i$ 的值为 $a_i$。您希望通过执行以下操作(至少一次),使操作后的每个顶点的值分别为 $b_1,b_2,⋯⋯,b_N$。 您每次可选 $1$ 条边。当选择的边连接顶点 $x$ 和顶点 $y$ 时,可进行以下任意一个操作。 让 $a_x-1,a_y+1$,或者让 $a_x+1,a_y-1$ 确定是否有操作可以达到您的目的。 ### 输入格式 第 $1$ 行:输入 $N,M$。 第 $2$ 行输入 $N$ 个数,$a_1,a_2,⋯⋯,a_N$。 第 3 行输入 $M$ 个数,$b_1,b_2,⋯⋯,b_M$。 第 4 至 $M+3$ 行,每行输入 $2$ 个数,$c_i,d_i$。 ### 输出格式 如果可以,输出 "Yes",否则,输出 "No"。

加入题单

上一题 下一题 算法标签: