问题 4741 --序列(本站数据)

4741: 序列(本站数据)

题目描述

  小 $D$ 有一个长度为 $n$ 的整数序列 $a_i$(下标从 $1$ 开始编号,下同),她想通过若干次操作把它变成序列 $b_i$。
小 $D$ 有 $m$ 种可选的操作,第 $i$ 种操作可使用三元组 $(t_i,u_i,v_i)$ 描述:
若 $t_i=1$,则她可以使 $a_{u_i}$ 与 $a_{v_i}$ 都加一或都减一;
若 $t_i=2$,则她可以使 $a_{u_i}$ 减一、$a_{v_i}$ 加一,或是 $a_{u_i}$ 加一、$a_{v_i}$ 减一,因此当 $u_i=v_i$ 时,这种操作相当于没有操作。
小 $D$ 可以以任意顺序执行操作,且每种操作都可进行无限次。
现在给定序列与所有操作,请你帮她判断是否存在一种方案能将 $a_i$ 变为 $b_i$。题目保证两个序列长度都为 $n$。
若方案存在请输出 `YES`,否则输出 `NO`。

输入

本题输入文件包含多组数据。
第一行一个正整数 $T$ 表示数据组数。
对于每组数据:
第一行两个整数 $n,m$,表示序列长度与操作种数。
第二行 $n$ 个整数表示序列 $a_i$。
第三行 $n$ 个整数表示序列 $b_i$。
接下来 $m$ 行每行三个整数 $t_i,u_i,v_i$,第 $i$ 行描述操作 $i$。
注意:同一个三元组 $(t_i,u_i,v_i)$ 可能在输入中出现多次。

输出

输出到文件 sequence.out 中。
对于每组数据输出一行一个字符串 `YES` 或 `NO` 表示答案。

样例输入输出

输入#1 复制
3
1 1
1
3
1 1 1
2 3
1 2
4 5
1 1 2
2 1 2
1 1 2
3 3
1 2 3
5 5 4
1 1 2
1 1 3
2 2 3
输出#1 复制
YES
YES
YES

提示

【样例1解释】
第一组数据:使用一次操作 $1$。
第二组数据:使用三次操作 $1$。
第三组数据:使用三次操作 $1$,令 $a_1,a_2$ 都增加 $3$,再使用一次操作 $2$,令 $a_1,a_3$ 都增加 $1$。
【数据范围与提示】
对于测试点 $1 \sim 5$:$n=2,m=1,a_i,b_i ≤ 99,u_1 ≠ v_1,t_1=1$。
对于测试点 $6 \sim 10$:$n=2,m=1,a_i,b_i ≤ 99,u_1 ≠ v_1,t_1=2$。
对于测试点 $11 \sim 12$:$n=2,a_i,b_i ≤ 99,u_i ≠ v_i$。
对于测试点 $13 \sim 16$:$t_i=2$。
对于测试点 $17$:$n,m ≤ 20$。
对于测试点 $18$:$n,m ≤ 1000$。
对于所有测试点:$1 ≤ T ≤ 10,1 ≤ n,m ≤ 10^5,1 ≤ a_i,b_i ≤ 10^9,t_i \in \lbrace 1,2 \rbrace,1 ≤ u_i,v_i ≤ n$。

序号 标题 作者 发表时间 费用 订购数 操作