Assumption is all you need
Time limit1sMemory limit1024 MB
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.
Problem
JB holds the belief that assumption is all you need to solve a problem. To prove it, JB gave you two permutations and of the numbers to . JB wants a sequence of element swap operations on such that:
- Every swapped pair forms an inversion when its operation is performed. That is, and at the moment of the -th operation.
- becomes 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 , the number of test cases. Each test case is given as follows.
The first line contains one integer (), the number of elements in and .
The second line contains distinct integers (), the array .
The third line contains distinct integers (), the array .
The sum of over all test cases does not exceed .
Output
For each test case, if no sequence exists, print one line containing the integer -1.
Otherwise, print the number of operations () on the first line. Then print lines, each with two integers and (), describing the -th operation .