Double Sort solution codeforces

Double Sort solution codeforces

You are given two arrays aa and bb, both consisting of nn integers.

In one move, you can choose two indices ii and jj (1i,jn1≤i,j≤niji≠j) and swap aiai with ajaj and bibi with bjbj. You have to perform the swap in both arrays.

You are allowed to perform at most 104104 moves (possibly, zero). Can you make both arrays sorted in a non-decreasing order at the end? If you can, print any sequence of moves that makes both arrays sorted.

Input

The first line contains a single integer tt (1t1001≤t≤100) — the number of testcases.

The first line of each testcase contains a single integer nn (2n1002≤n≤100) — the number of elements in both arrays.

The second line contains nn integers a1,a2,,ana1,a2,…,an (1ain1≤ai≤n) — the first array.

The third line contains nn integers b1,b2,,bnb1,b2,…,bn (1bin1≤bi≤n) — the second array.

Output

For each testcase, print the answer. If it’s impossible to make both arrays sorted in a non-decreasing order in at most 104104 moves, print -1. Otherwise, first, print the number of moves kk (0k104)(0≤k≤104). Then print ii and jj for each move (1i,jn(1≤i,j≤nij)i≠j).

If there are multiple answers, then print any of them. You don’t have to minimize the number of moves.

Example
input

Copy
3
2
1 2
1 2
2
2 1
1 2
4
2 3 1 2
2 3 2 3
output

Copy
0
-1
3
3 1
3 2
4 3

SOLUTION

Click here

Leave a Comment

Your email address will not be published.