Colors

Consider a connected undirected graph with $N$ nodes and $M$ edges. Initially every node $u$ has a color $a[u]$, encoded by an integer between $1$ and $N$. You can repeatedly modify node colors by assigning $a[u] = \min(a[u], a[v])$, where $u$ and $v$ are connected by an edge.

Task

Given a destination coloring $b[1] \dots b[N]$, determine whether you can transform $a$ into $b$.

Input data

There are several test cases per input file and you should answer each of them separately.

The first line contains the number of test cases. Each test case is structured as

N M
a[1] a[2] ... a[N]
b[1] b[2] ... b[N]
u1 v1
u2 v2
...
uM vM

Output data

For every test case you should print, on a separate line, 1 if $a$ can be transformed into $b$ using the above-mentioned operation and 0 otherwise.

Constraints and clarifications

• For all test cases, $N ≤ 150 \ 000$ and $M ≤ 200 \ 000$.
• For every input file, the sum of all $N$ is $≤ 300 \ 000$ and the sum of all $M$ is $≤ 400 \ 000$.
• $1 ≤ a[i], b[i] ≤ N$ for all $1 ≤ i ≤ N$.

Example

stdin

2
4 4
3 3 2 1
2 1 2 1
1 2
2 3
3 4
4 2
4 4
3 3 2 1
1 2 2 1
1 2
2 3
3 4
4 2

stdout

1
0

Explanation

For the first graph, the operations needed are:

• $a[2] = \min(a[2], a[3]) = 2$
• $a[1] = \min(a[1], a[2]) = 2$
• $a[2] = \min(a[2], a[4]) = 1$