Under construction

Still being built. Things may change

Assumption is all you need

Time limit1sMemory limit1024 MB

Summary
Given permutations A and B, output swaps that each undo an inversion of A to turn A into B, or report -1 if no sequence exists.
Level

Medium7 of 10

Topics
Array, Sorting, Greedy
Solved
No attempts yet

Problem

JB holds the belief that assumption is all you need to solve a problem. To prove it, JB gave you two permutations AA and BB of the numbers 11 to nn. JB wants a sequence of element swap operations (xi,yi)(x_i, y_i) on AA such that:

  1. Every swapped pair forms an inversion when its operation is performed. That is, xi<yix_i < y_i and Axi>AyiA_{x_i} > A_{y_i} at the moment of the ii-th operation.
  2. AA becomes BB after the last operation.

If no such sequence exists, determine that it is impossible. Help prove JB's belief by solving this problem!

Input

The first line contains one integer TT, the number of test cases. Each test case is given as follows.

The first line contains one integer nn (1≤n≤20211 \le n \le 2021), the number of elements in AA and BB.

The second line contains nn distinct integers A1,A2,…,AnA_1, A_2, \dots, A_n (1≤Ai≤n1 \le A_i \le n), the array AA.

The third line contains nn distinct integers B1,B2,…,BnB_1, B_2, \dots, B_n (1≤Bi≤n1 \le B_i \le n), the array BB.

The sum of nn over all test cases does not exceed 20212021.

Output

For each test case, if no sequence exists, print one line containing the integer -1.

Otherwise, print the number of operations kk (0≤k≤n(n−1)20 \le k \le \frac{n(n-1)}{2}) on the first line. Then print kk lines, each with two integers xix_i and yiy_i (1≤xi<yi≤n1 \le x_i < y_i \le n), describing the ii-th operation swap(Axi,Ayi)\text{swap}(A_{x_i}, A_{y_i}).

Examples1

  1. Example 1

    Input
    3
    2
    1 2
    2 1
    4
    4 1 2 3
    1 3 2 4
    8
    8 7 6 5 4 3 2 1
    1 8 7 6 5 4 3 2
    
    Expected output
    -1
    2
    1 2
    2 4
    7
    7 8
    6 7
    5 6
    4 5
    3 4
    2 3
    1 2