有两张边集相同的图 $A,B$，每个点都是红黑二色之一，并且带着点权 $a_i$。
你可以执行以下操作零次或任意次：
- 选择一张图和相邻的两个点 $u,v$。
- 交换 $a_u$ 和 $a_v$。
- 如果 $u$ 和 $v$ 同色，则将他们同时反色，否则颜色保持不变。
你想要知道，两张图能否变得相同，即所有点的颜色和点权对应相同。
输入格式
本题多测。
第一行包含一个整数 $T$ 表示数据组数。
对于每组数据：
第一行两个整数 $n,m$ 表示点的个数和边的个数。
接下来 $m$ 行每行两个整数 $u,v$ 表示一条边。
接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示 $A$ 上第 $i$ 个点的点权。
接下来一行一个长为 $n$ 的字符串，第 $i$ 个字符 $c_i$ 表示 $A$ 上第 $i$ 个点的颜色，为 R 或 B。
接下来一行 $n$ 个整数，第 $i$ 个整数 $b_i$ 表示 $B$ 上第 $i$ 个点的点权。
接下来一行一个长为 $n$ 的字符串，第 $i$ 个字符 $d_i$ 表示 $B$ 上第 $i$ 个点的颜色，为 R 或 B。
输出格式
对于每组数据，输出一行，YES 表示两张图可以变得相同，NO 表示不能。
样例一
input
3 2 1 1 2 3 4 RR 4 3 BB 3 2 1 2 2 3 1 1 1 RBR 1 1 1 BBB 3 3 1 2 2 3 3 1 1 1 1 RBR 1 1 1 BBB
output
YES NO YES
数据范围与提示
| 测试点编号 | $n\leq$ | $\sum n\leq$ | 特殊性质 |
|---|---|---|---|
| $1\sim 2$ | $5$ | $500$ | 无 |
| $3\sim 4$ | $10^6$ | $10^6$ | 保证图是二分图 |
| $5\sim 7$ | 保证图连通且不是二分图 | ||
| $8\sim 10$ | 无 |
对于所有数据，保证 $1\leq T\leq 3\times 10^4, 1\leq n,\sum n\leq 10^6, 0\leq m, \sum m\leq 10^6, 1\leq u, v\leq n, 0\leq a_i, b_i\leq 10^9, c_i, d_i\in \{'R', 'B'\}$，图中无重边无自环。
时间限制：$2\texttt{s}$
空间限制：$512\texttt{MB}$