Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

#21688. 【NOIP Round #2】图同构

Statistics

有两张边集相同的图 $A,B$,每个点都是红黑二色之一,并且带着点权 $a_i$。

你可以执行以下操作零次或任意次:

  1. 选择一张图和相邻的两个点 $u,v$。
  2. 交换 $a_u$ 和 $a_v$。
  3. 如果 $u$ 和 $v$ 同色,则将他们同时反色,否则颜色保持不变。

你想要知道,两张图能否变得相同,即所有点的颜色和点权对应相同。

输入格式

本题多测。

第一行包含一个整数 $T$ 表示数据组数。

对于每组数据:

第一行两个整数 $n,m$ 表示点的个数和边的个数。

接下来 $m$ 行每行两个整数 $u,v$ 表示一条边。

接下来一行 $n$ 个整数,第 $i$ 个整数 $a_i$ 表示 $A$ 上第 $i$ 个点的点权。

接下来一行一个长为 $n$ 的字符串,第 $i$ 个字符 $c_i$ 表示 $A$ 上第 $i$ 个点的颜色,为 RB

接下来一行 $n$ 个整数,第 $i$ 个整数 $b_i$ 表示 $B$ 上第 $i$ 个点的点权。

接下来一行一个长为 $n$ 的字符串,第 $i$ 个字符 $d_i$ 表示 $B$ 上第 $i$ 个点的颜色,为 RB

输出格式

对于每组数据,输出一行,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}$