#y0004. 士兵游荡之一

    ID: 9989 传统题 1000ms 256MiB 尝试: 122 已通过: 15 难度: 5 上传者: 标签>CF1800普及+/提高-二分图建模最大流Dinic残量网络当前弧优化

士兵游荡之一

题目描述

在该国有 nn 个城市和 mm 条双向道路连接它们。每个城市都有一支军队。第 ii 个城市的军队由 aia_i 名士兵组成。现在士兵们在游荡。游荡后,每名士兵必须要么留在自己的城市,要么通过最多沿一条道路移动前往邻近的城市。

检查在游荡后,第 ii 个城市是否可能正好有 bib_i 名士兵。

输入格式

输入 输入的第一行包含两个整数 nn 和 mm (1 ≤ n ≤ 100,0 ≤ m ≤ 200)( 1 ≤ n ≤ 100 , 0 ≤ m ≤ 200 )。 下一行包含 n 个整数 a1, a2, ⋯ , an(0 ≤ ai ≤ 100)a_1, a_2, \cdots, a_n ( 0 ≤ a_i ≤ 100 )。

再下一行包含 nn 个整数 b1, b2, ⋯ , bn(0 ≤ bi ≤ 100)b_1, b_2, \cdots, b_n ( 0 ≤ b_i ≤ 100 )。

接下来有 mm 行,每行包含两个整数 pp 和 q(1 ≤ p, q ≤ n,p ≠ q)q ( 1 ≤ p, q ≤ n , p ≠ q ),表示城市 pp 和 qq 之间有一条无向道路。

输出格式

如果无法满足条件,则输出 NO。 否则输出 YES。

样例 #1

样例输入 #1

4 4
1 2 6 3
3 5 3 1
1 2
2 3
3 4
4 2

样例输出 #1

YES

样例 #2

样例输入 #2

2 0
1 2
2 1

样例输出 #2

NO