시간 제한메모리 제한제출정답맞은 사람정답 비율
3 초 512 MB0000.000%

문제

As a modern art lover, Nocriz loves going to the Power Station of Art.

Currently, art pieces of a modern genre of art called "red-black graphs" are exhibited in the Power Station of Art. Every red-black graph art piece is an undirected labeled graph with numbers and colors associated with each vertex. Each vertex is either red or black.

It is possible to modify a graph in the following way: choose an edge and swap the numbers written on the corresponding vertices. In addition, if the colors of the two vertices are the same, the colors of both vertices are changed (from red to black or from black to red). Otherwise, the colors of the two vertices remain unchanged.

Now, Nocriz is studying two art pieces. The graphs are the same but the numbers and colors may be different. Is it possible to make some (possibly zero) modifications to the art pieces to make them be the same?

입력

The first line contains an integer $T$ ($1 \le T \le 3 \cdot 10^4$), the number of test cases. Then $T$ test cases follow.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^6$, $0 \le m \le 10^6$), the number of vertices and edges.

Then $m$ lines follow, each of them contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$) representing an edge. It is guaranteed that there are no multiple edges in the input, and the graph may be unconnected.

Then numbers and colors of the two graphs follow. For each graph:

The first line contains $n$ integers, the $i$-th integer $a_i$ ($0 \le a_i \le 10^6$) representing the number written on the $i$-th vertex of the graph.

The second line contains $n$ characters. If the $i$-th character is 'R', the $i$-th vertex is red. If the $i$-th character is 'B', the $i$-th vertex is black.

It is guaranteed that $\sum n \le 10^6$ and $\sum m \le 10^6$.

출력

For each test case, output a single line containing "YES" if it is possible to make some (possibly zero) modifications to the art pieces to make them be the same, or "NO" otherwise.

예제 입력 1

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

예제 출력 1

YES
NO
YES