F. To Sort, and Not to Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hong Kong's outlying islands are a collection of over 250 islands scattered across its surrounding waters, each offering unique charm and attractions. While some, like Lantau Island, are well-known and bustling with activity, others remain tranquil and largely untouched, perfect for those seeking nature, hiking, or a glimpse into traditional village life. These islands are connected by ferry services, making them popular day-trip destinations for both locals and tourists. Their diverse landscapes, from sandy beaches to lush mountains, provide a striking contrast to Hong Kong's urban core.

Different views of Lamma Island, Yung Shue Wan and Sok Kwu Wan side (© The HK HUB)

Imagine Hong Kong has $$$N$$$ outlying islands, and two different tour itineraries — Tour A and Tour B — have been planned. Each itinerary lists the islands in a unique order, represented by two permutations $$$A$$$ and $$$B$$$ of the numbers $$$1$$$ through $$$N$$$.

In each operation, you can select a subarray in both tours, say from the $$$l$$$-th to $$$r$$$-th islands that will be visited (with $$$1 \leq l \leq r \leq N$$$), and reorganize the visiting order for that subarray in both tours by sorting it in increasing order. Your challenge is to adjust the itineraries so that Tour A ends up visiting the islands in perfect ascending order, while Tour B does not. Determine whether this is possible, and if so, construct a sequence of operations that achieves the goal using the minimum number of operations.

More formally, you are given $$$2$$$ permutations $$$A$$$ and $$$B$$$ with length $$$N$$$. In each operation, you can pick $$$2$$$ integers $$$1 \leq l \leq r \leq N$$$ and sort the subarrays $$$A[l..r]$$$ and $$$B[l..r]$$$ (inclusive) simultaneously. Determine whether you can successfully sort $$$A$$$ but not $$$B$$$, and if so, provide a construction using the minimum number of operations.

Input

Each test contains multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$N$$$ ($$$3 \leq N \leq 1000$$$) — the length of the permutations.

The second line of each test case contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \leq A_i \leq N$$$) — the permutation $$$A$$$. It is guaranteed that $$$A$$$ forms a permutation.

The third line of each test case contains $$$N$$$ integers $$$B_1, B_2, \dots, B_N$$$ ($$$1 \leq B_i \leq N$$$) — the permutation $$$B$$$. It is guaranteed that $$$B$$$ forms a permutation.

It is guaranteed that the sum of the values of $$$N$$$ across all test cases does not exceed $$$5000$$$.

Output

For each test case, print -1 if it is impossible to sort $$$A$$$ but not $$$B$$$.

Otherwise, on the first line, print $$$q$$$ ($$$q \geq 0$$$), the minimum number of operations to do so. Then, for the next $$$q$$$ lines, print $$$l$$$ and $$$r$$$, the ranges for the operation. If there are multiple answers, print any.

Example
Input
5
4
1 2 3 4
4 3 2 1
4
1 3 2 4
1 2 4 3
4
4 2 1 3
1 3 4 2
4
3 4 1 2
1 3 2 4
3
1 2 3
1 2 3
Output
0
1
2 3
2
1 3
3 4
-1
-1
Note

In the first set of input data, $$$a$$$ is already sorted but $$$b$$$ isn't. Hence the answer is $$$0$$$.

In the second set of input data, after the operations, $$$a = $$$ 1 2 3 4 and $$$b = $$$ 1 2 4 3. Since $$$a$$$ is not sorted initially, $$$1$$$ is the minimum number of operations to sort $$$a$$$ and not $$$b$$$.

In the third set of input data, after the operations, $$$a = $$$ 1 2 3 4 and $$$b = $$$ 1 4 2 3. It can be proven that $$$2$$$ is the minimum number of operations required.

In the fourth and fifth set of input data, it can be proven that it is impossible to sort $$$a$$$ and not $$$b$$$. Hence the answer is $$$-1$$$.