You are given two strongly connected†
 directed graphs, each with exactly 𝑛
 vertices, but possibly different numbers of edges. Upon closer inspection, you noticed an important feature — the length of any cycle in these graphs is divisible by 𝑘
.

Each of the 2𝑛
 vertices belongs to exactly one of two types: incoming or outgoing. For each vertex, its type is known to you.

You need to determine whether it is possible to draw exactly 𝑛
 directed edges between the source graphs such that the following four conditions are met:

The ends of any added edge lie in different graphs.
From each outgoing vertex, exactly one added edge originates.
Into each incoming vertex, exactly one added edge enters.
In the resulting graph, the length of any cycle is divisible by 𝑘
.
†
A strongly connected graph is a graph in which there is a path from every vertex to every other vertex.

Input
Each test consists of multiple test cases. The first line contains a single integer 𝑡
 (1≤𝑡≤104
) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers 𝑛
 and 𝑘
 (2≤𝑘≤𝑛≤2⋅105
) — the number of vertices in each graph and the value by which the length of each cycle is divisible.

The second line of each test case contains 𝑛
 integers 𝑎1,𝑎2,…,𝑎𝑛
 (𝑎𝑖∈{0,1}
). If 𝑎𝑖=0
, then vertex 𝑖
 of the first graph is incoming. If 𝑎𝑖=1
, then vertex 𝑖
 of the first graph is outgoing.

The third line of each test case contains a single integer 𝑚1
 (1≤𝑚1≤5⋅105
) — the number of edges in the first graph.

The next 𝑚1
 lines contain descriptions of the edges of the first graph. The 𝑖
-th of them contains two integers 𝑣𝑖
 and 𝑢𝑖
 (1≤𝑣𝑖,𝑢𝑖≤𝑛
) — an edge in the first graph leading from vertex 𝑣𝑖
 to vertex 𝑢𝑖
.

Next, in the same format, follows the description of the second graph.

The next line contains 𝑛
 integers 𝑏1,𝑏2,…,𝑏𝑛
 (𝑏𝑖∈{0,1}
). If 𝑏𝑖=0
, then vertex 𝑖
 of the second graph is incoming. If 𝑏𝑖=1
, then vertex 𝑖
 of the second graph is outgoing.

The next line contains a single integer 𝑚2
 (1≤𝑚2≤5⋅105
) — the number of edges in the second graph.

The next 𝑚2
 lines contain descriptions of the edges of the second graph. The 𝑖
-th of them contains two integers 𝑣𝑖
 and 𝑢𝑖
 (1≤𝑣𝑖,𝑢𝑖≤𝑛
) — an edge in the second graph leading from vertex 𝑣𝑖
 to vertex 𝑢𝑖
.

It is guaranteed that both graphs are strongly connected, and the lengths of all cycles are divisible by 𝑘
.

It is guaranteed that the sum of 𝑛
 over all test cases does not exceed 2⋅105
. It is guaranteed that the sum of 𝑚1
 and the sum of 𝑚2
 over all test cases does not exceed 5⋅105
.

Output
For each test case, output "YES" (without quotes) if it is possible to draw 𝑛
 new edges such that all conditions are met, and "NO" (without quotes) otherwise.

You may output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Example
InputCopy
3
4 2
1 0 0 1
4
1 2
2 3
3 4
4 1
1 0 0 1
4
1 3
3 2
2 4
4 1
3 3
0 0 0
3
1 2
2 3
3 1
1 1 0
3
1 2
2 3
3 1
4 2
1 1 1 1
4
1 2
2 3
3 4
4 1
0 0 0 0
6
1 2
2 1
1 3
3 1
1 4
4 1
OutputCopy
YES
NO
YES
Note
In the first test case, it is possible to draw edges from the first graph to the second graph as (1,3)
 and (4,2)
 (the first number in the pair is the vertex number in the first graph, and the second number in the pair is the vertex number in the second graph), and from the second graph to the first graph as (1,2)
, (4,3)
 (the first number in the pair is the vertex number in the second graph, and the second number in the pair is the vertex number in the first graph).

In the second test case, there are a total of 4
 incoming vertices and 2
 outgoing vertices, so it is not possible to draw 3
 edges.

solve this problem c++