Double Sort (Codeforces 1681C)
Tags: Implement, sortings

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 \le i, j \le n$$$; $$$i \neq j$$$) and swap $$$a_i$$$ with $$$a_j$$$ and $$$b_i$$$ with $$$b_j$$$. You have to perform the swap in both arrays.You are allowed to perform at most $$$10^4$$$ 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 \le t \le 100$$$) — the number of testcases.The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of elements in both arrays.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the first array.The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 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 \le k \le 10^4)$$$. Then print $$$i$$$ and $$$j$$$ for each move $$$(1 \le i, j \le n$$$; $$$i \neq j)$$$.If there are multiple answers, then print any of them. You don't have to minimize the number of moves.


Sample Inputs:
3
2
1 2
1 2
2
2 1
1 2
4
2 3 1 2
2 3 2 3

Sample Outputs:
0
-1
3
3 1
3 2
4 3

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    X = list(zip(a, b))
    Y = list(zip(sorted(a), sorted(b)))
    if Y == sorted(X):
        X_i = sorted((x + (i,) for (i, x) in enumerate(X)))
        a_index = list(range(n))
        b_index = [x[2] for x in X_i]
        moves = []
        for j in range(n):
            if a_index[j] == b_index[j]:
                continue
            a_i = j
            b_i = a_index.index(b_index[j])
            moves.append((a_i, b_i))
            (a_index[a_i], a_index[b_i]) = (a_index[b_i], a_index[a_i])
        print(len(moves))
        if len(moves) > 0:
            print('\n'.join((f'{x + 1} {y + 1}' for (x, y) in moves)))
    else:
        print(-1)

Solution (Python):
for tcase in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = [(ai, bi, i) for (i, (ai, bi)) in enumerate(zip(a, b))]
    ab.sort()
    for j in range(n):
        (ai, bi, i) = ab[j]
        if i != j and ab[i][0] == ai and (ab[i][1] == bi):
            (ab[i], ab[j]) = (ab[j], ab[i])
    a = [ai for (ai, bi, i) in ab]
    b = [bi for (ai, bi, i) in ab]
    if all((a[j] <= a[j + 1] and b[j] <= b[j + 1] for j in range(n - 1))):
        ans = []
        p = [i for (ai, bi, i) in ab]
        for j in range(n):
            s = [j]
            i = p[j]
            while i != j:
                s.append(i)
                i = p[i]
            k = s.pop()
            while len(s) > 0:
                i = s.pop()
                ans.append((i, k))
                (p[i], p[k]) = (p[k], p[i])
                k = i
        if len(ans) <= 10 ** 4:
            print(len(ans))
            while len(ans) > 0:
                (i, j) = ans.pop()
                print(j + 1, i + 1)
        else:
            print(-1)
    else:
        print(-1)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().strip()

def is_sorted(a):
    last = a[0]
    for i in a:
        if i < last:
            return False
        last = i
    return True

def good(ab):
    a = [l for (l, r) in ab]
    b = [r for (l, r) in ab]
    return is_sorted(a) and is_sorted(b)

def get_sort_seq(ab, ab_sorted):
    idx = 0
    ans = []
    for pair in ab_sorted:
        cur = ab[idx:].index(pair) + idx
        if cur != idx:
            (ab[idx], ab[cur]) = (ab[cur], ab[idx])
            ans.append((cur + 1, idx + 1))
        idx += 1
    return ans
for _ in range(int(input())):
    n = int(input())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]
    ab = [*zip(a, b)]
    ba = [*zip(b, a)]
    if good(sorted(ab)):
        sort_seq = get_sort_seq(ab, sorted(ab))
    elif good(sorted(ba)):
        sort_seq = get_sort_seq(ba, sorted(ba))
    else:
        sort_seq = -1
    if sort_seq == -1:
        print(-1)
    else:
        print(len(sort_seq))
        for pair in sort_seq:
            print(*pair)