A. Tokens on a Graph
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a graph consisting of $$$n$$$ vertices numbered with integers from $$$1$$$ to $$$n$$$, connected by $$$n+m$$$ edges. The first $$$n$$$ edges connect neighboring vertices, meaning the $$$i$$$-th edge connects the $$$i$$$-th and $$$(i+1)$$$-th vertices, and the $$$n$$$-th edge connects the $$$n$$$-th and $$$1$$$-st vertices. In some vertices, there are $$$n-2$$$ tokens numbered with integers from $$$1$$$ to $$$n-2$$$, and no vertex can have more than one token.

In one move, you are allowed to move any token to a vertex connected by an edge to its current vertex, provided that there is currently no token in that vertex. For each token, you know which vertex it should end up in after all moves are completed.

Your task is to determine the sequence of moves so that the tokens end up in the required positions. Note that minimizing the number of moves is not required.

Input

Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 20$$$) — the number of sets of input data. The description of the sets of input data follows.

In the first line of each set of input data, two integers $$$n$$$ and $$$m$$$ ($$$4 \le n \le 100$$$, $$$1 \le m \le 2\,000$$$) are given — the number of vertices and additional edges, respectively.

The second line contains $$$n-2$$$ integers $$$a_i$$$ ($$$1 \le a_i \le n$$$, $$$a_i \ne a_j$$$ for $$$i \ne j$$$), where the $$$i$$$-th number indicates the initial position of the $$$i$$$-th token.

The third line contains $$$n-2$$$ integers $$$b_i$$$ ($$$1 \le b_i \le n$$$, $$$b_i \ne b_j$$$ for $$$i \ne j$$$), where the $$$i$$$-th number indicates the required position of the $$$i$$$-th token.

In the following $$$m$$$ lines, two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) are given — the numbers of the vertices connected by an edge. It is guaranteed that the resulting graph does not contain multiple edges or self-loops.

It is guaranteed that the sum of $$$n$$$ across all sets of input data does not exceed $$$100$$$.

Output

For each set of input data, output a single integer $$$k$$$ ($$$k \ge 0$$$) in the first line — the number of moves. In the following $$$k$$$ lines, output two integers $$$c_i$$$ and $$$p_i$$$ ($$$1 \le c_i \le n - 2$$$, $$$1 \le p_i \le n$$$) — the token number and the vertex to which it should be moved on the $$$i$$$-th move, respectively.

The total number of moves across all sets of input data must not exceed $$$2 \cdot 10^6$$$. It is guaranteed that such an answer always exists.

Example
Input
1
4 1
1 3
2 1
2 4
Output
3
2 4
1 2
2 1