Igor Perić

You are given two arrays a and b, both consisting of n integers.

In one move, you can choose two indices i and j (1≤i,j≤n; i≠j) and swap ai with aj and bi with bj. You have to perform the swap in both arrays.

You are allowed to perform at most 104 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 t (1≤t≤100) — the number of testcases.

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

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

The third line contains n integers b1,b2,…,bn (1≤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 10^4 moves, print -1. Otherwise, first, print the number of moves k (0≤k≤104). Then print i and j for each move (1≤i,j≤n; i≠j).

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

Example input

3
2
1 2
1 2
2
2 1
1 2
4
2 3 1 2
2 3 2 3

Example output

0
-1
3
3 1
3 2
4 3

Solution

Knowing we’re asked to sort the array in at most 10^4 steps, and limit for N is 10^2, we can get away with an O(N^2) solution… Bubble sort to the rescue! 🙂

When implementing bubble sort we will try to sort primarily on the values of A, and resolve the ties with sorting on the respective values of B. If this yields sorted A and B, it is safe to print out the swaps performed during the bubble sort, or -1 otherwise.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

int main(){

    int t;
    cin >> t;
    while (t--) {

        int n;
        cin >> n;
        vector<int> a(n), b(n);
        for (int i=0;i<n;i++) cin >> a[i];
        for (int i=0;i<n;i++) cin >> b[i];

        vector< pair<int, int> > sol;
        for (int i=0;i<n;i++) {
            for (int j=i+1;j<n;j++) {
                if (a[j] < a[i] || (a[j] == a[i] && b[j] < b[i])) {
                    swap(a[i], a[j]);
                    swap(b[i], b[j]);
                    sol.push_back({ i + 1, j + 1 });
                }
            }
        }

        // check if B is sorted
        int i=1;
        for (;i<n;i++) {
            if (b[i] < b[i-1]) break;
        }
        if (i < n) {
            cout << -1 << endl;
            continue;
        }

        // solution is possible (ignore 10^4 limit, n = 100)
        cout << sol.size() << endl;
        for (int i=0;i<sol.size();i++) cout << sol[i].first << " " << sol[i].second << endl;

    }
    return 0;
}