시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

ZZX has a sequence of boxes numbered $1, 2, \ldots, n$. Each box can contain at most one ball.

You are given the initial configuration of the balls. For $1 \le i \le n$, if the $i$-th box is empty, then $a_i = 0$, otherwise the $i$-th box contains exactly one ball, the color of which is $a_i$, a positive integer. Balls of the same color cannot be distinguished.

ZZX will perform $m$ operations in order. During $i$-th operation, he collects all the balls from boxes $l_i, l_i + 1, \ldots, r_i - 1, r_i$, and then arbitrarily puts them back into these boxes. Note that each box should always contain at most one ball.

ZZX wants to change the configuration of the balls from $a_1, a_2, \ldots, a_n$ to $b_1, b_2, \ldots, b_n$ using these operations. Please tell ZZX whether it is possible to achieve his goal.

입력

The first line contains an integer $T \le 60$. Then $T$ test cases follow. In each test case:

The first line of the test case contains two integers $n$ and $m$ ($1 \le n \le 1000$, $0 \le m \le 1000$, sum of $n$ over all test cases does not exceed $2000$, sum of $m$ over all test cases does not exceed $2000$).

The second line contains $a_1, a_2, \ldots ,a_n$ ($0 \le a_i \le n$). The third line contains $b_1, b_2, \ldots, b_n$ ($0 \le b_i \le n$). Each of the next $m$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).

출력

For each test case, print "Yes" or "No" on a separate line.

예제 입력 1

5
4 1
0 0 1 1
0 1 1 1
1 4
4 1
0 0 1 1
0 0 2 2
1 4
4 2
1 0 0 0
0 0 0 1
1 3
3 4
4 2
1 0 0 0
0 0 0 1
3 4
1 3
5 2
1 1 2 2 0
2 2 1 1 0
1 3
2 4

예제 출력 1

No
No
Yes
No
Yes