F. Shift and Slide
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a connected undirected graph with $$$n$$$ vertices. The vertices contain the values $$$1, 2, \ldots, n$$$, each value exactly once.

In one operation, you may choose an edge $$$(u, v)$$$ and swap the values on vertices $$$u$$$ and $$$v$$$ if and only if the two values differ by exactly $$$1$$$.

You are given the initial values $$$a_1, a_2, \ldots, a_n$$$ and the target values $$$b_1, b_2, \ldots, b_n$$$. Determine whether it is possible to obtain the target values after applying zero or more operations.

Note that the input and output sizes are large, so using fast I/O is recommended.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case begins with a line containing two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 1000$$$, $$$n - 1 \le m \le \frac{n(n-1)}{2}$$$) — the number of vertices and edges.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), denoting an undirected edge. The graph is connected and contains no multiple edges.

The next line contains a permutation $$$a_1, a_2, \ldots, a_n$$$ of $$$1, 2, \ldots, n$$$.

The next line contains a permutation $$$b_1, b_2, \ldots, b_n$$$ of $$$1, 2, \ldots, n$$$.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, if the target values cannot be obtained, print NO.

Otherwise, print YES. Then print an integer $$$k$$$ ($$$0 \le k \le n^2$$$) – the number of swaps. Each of the next $$$k$$$ lines must contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), meaning that you swap the values on vertices $$$u$$$ and $$$v$$$ at this step. For every printed swap, vertices $$$u$$$ and $$$v$$$ must be connected by an edge, and their values immediately before the swap must differ by exactly $$$1$$$. After all printed swaps, the values must be equal to the target permutation.

It is guaranteed that if a solution exists, then there exists one with at most $$$n^2$$$ swaps.

You may print YES and NO in any case. For example, yes, Yes, and YES are all accepted.

Example
Input
4
3 2
1 2
2 3
2 1 3
1 2 3
3 2
1 2
2 3
1 2 3
3 2 1
4 6
1 2
1 3
1 4
2 3
2 4
3 4
1 4 2 3
3 2 4 1
5 4
1 2
1 3
1 4
1 5
1 2 3 4 5
5 1 2 3 4
Output
YES
1
2 1
NO
YES
4
3 4
1 4
3 2
1 2
YES
4
1 2
1 3
1 4
1 5
Note

In the first test case, the initial values are $$$(2,1,3)$$$. The values on vertices $$$1$$$ and $$$2$$$ differ by $$$1$$$, and vertices $$$1$$$ and $$$2$$$ are connected by an edge, so we can swap them and obtain $$$(1,2,3)$$$.

In the second test case, it can be shown that the target values cannot be obtained.

In the third test case, one valid sequence of swaps is shown in the sample output.

In the fourth test case, the graph is a star centered at vertex $$$1$$$. Starting from $$$(1,2,3,4,5)$$$, perform the swaps along edges $$$(1,2)$$$, then $$$(1,3)$$$, then $$$(1,4)$$$, then $$$(1,5)$$$. The values after these swaps are $$$(5,1,2,3,4)$$$, which is the target permutation.