[Solution] Double Sort Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Double Sort Codeforces Solution | Codeforces Problem Solution 2022

C. Double Sort

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

Solution Click Below:-  CLICK HERE

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

Double Sort Codeforces Solution

Game with Cards Codeforces Solution

Card Trick Codeforces Solution

Labyrinth Adventures Codeforces Solution

Unique Occurrences Codeforces Solution

Required Length Codeforces Solution

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

The second line contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤n$1\le a_i\le n$) — the first array.

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

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